为什么无限RE。。。。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 220;
const int INF = 111111111;
using namespace std;



struct  EdmoundsKarp{
    struct Edge{
        int from, to, cap, flow;
        Edge(int a, int b, int c, int d) :from(a), to(b), cap(c), flow(d) {}
        Edge(){}
    };

    int n, m;
    vector<Edge> edges;//边数两倍
    vector<int> G[maxn];//G[i][j]表示i的第j条边在edges中的编号
    int a[maxn];//增量
    int p[maxn];

    void init(int n){
        this->n = n;
        for(int i = 0;i<n;i+=1) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int cap){
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    int MaxFlow(int s, int t){
        int flow = 0;
        for (;;){
            Mem(a, 0);
            queue<int> Q;
            Q.push(s);
            a[s] = INF;
            while (!Q.empty()){//实际上每次BFS目的只是找到一条增广路
                int x = Q.front(); Q.pop();
                for (int i = 0; i<G[x].size(); i += 1){
                    Edge & e = edges[G[x][i]];
                    if (!a[e.to] && e.cap > e.flow){
                        p[e.to] = G[x][i];
                        a[e.to] = min(a[x], e.cap - e.flow);
                        Q.push(e.to);
                    }
                }
                if (a[t]) break;//如果到汇点的增量不为0证明增广路径已经找到
            }
            if (!a[t]) break;//如果枚举全部的边,汇点的增量也只能是0,证明已经是最大流
            for (int u = t; u != s; u = edges[p[u]].from){
                edges[p[u]].flow += a[t];
                edges[p[u] ^ 1].flow -= a[t];
            }
            flow += a[t];
        }
        return flow;
    }
};


bool Judge(int A, int B) {
    int* pMax = (A > B) ? &A : &B;
    while (*pMax > 0) {
        int nLast_A = A & 1;
        int nLast_B = B & 1;

        if (nLast_A == nLast_B) return false;

        if (A > 0) A >>= 1;
        if (B > 0) B >>= 1;
    }

    return true;
}

int main(){
    EdmoundsKarp D;
    int n, m;
    vector<int> A, B;
    scanf("%d %d", &n, &m);
    if (n < m) swap(n, m);  
    A = vector<int>(n); B = vector<int>(m);
    for (int i = 0; i < n; i += 1) scanf("%d", &A[i]);
    for (int i = 0; i < m; i += 1)scanf("%d", &B[i]);
    int S = 28, T = 29;
    D.init(30);
    for (int i = 0; i < n; i += 1)
        for (int j = 0; j < m; j += 1){
            if (Judge(A[i],B[j]))
                D.AddEdge(A[i], B[j], 1);
        }
    for (int i = 0; i < n; i += 1) D.AddEdge(S, A[i], 1);
    for (int i = 0; i < m; i += 1) D.AddEdge(B[i], T, 1);
    int ans = D.MaxFlow(S, T);
    if(ans) printf("%d\n", ans);
    else printf("I want nobody nobody but you\n");
    Sy;
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
1693
难度
7
分类
图结构 | 二分图匹配 点击显示
标签
递交数
2047
已通过
352
通过率
17%
被复制
3
上传者