[最大流法二分比對]uva753

很巧妙的用數組存儲c和f友善

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 310;
const int INF = 0x3c3c3c3c;
string str;
map<string,int> rs,dv;
int mr[MAXN];//從源點到i的最小殘量
int p[MAXN];//更新時i的上流節點
int c[MAXN][MAXN],f[MAXN][MAXN];
int maxFlow(int op,int ed,int n){
    queue<int>q;
    memset(f,0,sizeof(f));
    memset(p,0,sizeof(p));
    int F=0;
    while(1){
        memset(mr,0,sizeof(mr));
        q.push(op);
        mr[op]=INF;//源點殘量
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v=0;v<n;v++){
                if(!mr[v]&&c[u][v]>f[u][v]){
                    p[v]=u;
                    q.push(v);
                    mr[v]=min(mr[u],c[u][v]-f[u][v]);
                }
            }
        }
        if(mr[ed]==0) return F;
        for(int u=ed;u!=op;u=p[u]){
            f[u][p[u]]-=mr[ed];
            f[p[u]][u]+=mr[ed];
        }
        F+=mr[ed];
    }
}
int main()
{
    int t;
    int n,m,k,did,rid,adt; //adt是多出來的接口數量
    scanf("%d",&t);
    while(t--){
        rs.clear();
        dv.clear();
        memset(c,0,sizeof(c));
        adt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cin>>str;
            rs[str]=i;
        }
        scanf("%d",&m);
        for(int i=1;i<=m;i++){

            cin>>str;
            if((did=dv[str])==0) did=(dv[str]=i);
            c[0][did]+=1;
            cin>>str;
            if((rid=rs[str])==0){
                adt++;
                rid=(rs[str]=n+adt);
            }
            c[did][rid+m]+=1;

        }
        for(int i=m+1;i<=m+n;i++)
            c[i][m+n+adt+1]+=1;
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            cin>>str;
            rid=rs[str];
            cin>>str;
            c[m+rid][m+rs[str]]+=INF;
        }
        int ans=maxFlow(0,m+n+adt+1,m+n+adt+2);
        printf("%d\n",m-ans);
        if(t) puts("");
    }
    return 0;
}