I-Interesting Computer Game

链接：https://ac.nowcoder.com/acm/contest/5673/I
来源：牛客网

题意：

t组样例，给你n对数，让你从每对数中任选一个数，限制条件是，如果这对数中的某个数选过，你就不能选这个数，两个都选过，那么就两个都不选，问你最多能选几个数

solution：

我们把每对数记作一个回合，每个回合与当前这队数相连，通过网络流求解一般图的最大匹配

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
int T,n;
int sx,tx;
int head[400010];
int cur[400010];
int deep[500010];
int a[100010],b[100010];
int cnt;
unordered_map<int,int>mp;
struct Edge
{
    int to,w,next;
}edge[1000010];
void add_edge(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int dfs(int u,int flow)
{
    if(u==tx)return flow;
    for(int& i=cur[u];i!=-1;i=edge[i].next)
    {
        if(deep[edge[i].to]==deep[u]+1&&edge[i].w!=0)
        {
            int d=dfs(edge[i].to,min(flow,edge[i].w));
            if(d>0)
            {
                edge[i].w-=d;
                edge[i^1].w+=d;
                return d;
            }
        }
    }
    return 0;
}
int bfs()
{
    queue<int>q;
    while(!q.empty())q.pop();
    memset(deep,0,sizeof(deep));
    deep[sx]=1;
    q.push(sx);
    do{
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            if(deep[edge[i].to]==0&&edge[i].w>0)
            {
                deep[edge[i].to]=deep[u]+1;
                q.push(edge[i].to);
                if(edge[i].to==tx)return 1;
            }
        }
    }while(!q.empty());
    if(deep[tx]>0)return 1;
    return 0;
}
int Dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=1;i<=tx;i++)cur[i]=head[i];
        while(int d=dfs(sx,INF))
            ans+=d;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    for(int num=1;num<=T;num++)
    {
        scanf("%d",&n);
        cnt=0;
        mp.clear();
        memset(head,-1,sizeof(head));
        int c=1;

        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
            if(mp[a[i]]==0)mp[a[i]]=c++;
            if(mp[b[i]]==0)mp[b[i]]=c++;
            a[i]=mp[a[i]];
            b[i]=mp[b[i]];
        }
        sx=c+n+2;
        //cout<<c<<endl;
        for(int i=1;i<=n;i++)
        {
            int u=a[i],v=b[i];
            //cout<<u<<' '<<v<<endl;
            add_edge(i,u+n,1);
            add_edge(u+n,i,0);
            add_edge(i,v+n,1);
            add_edge(v+n,i,0);
            add_edge(sx,i,1);
            add_edge(i,sx,0);
        }
        tx=sx+1;//cout<<sx<<' '<<tx<<endl;
        for(int i=1;i<c;i++)
        {
            add_edge(i+n,tx,1);
            add_edge(tx,i+n,0);
        }
        int ans=Dinic();
        printf("Case #%d: %d\n",num,ans);
    }
    return 0;
}