2020牛客暑期多校训练营（第八场）I

题目描述

  Apollo is playing an interesting computer game. There are rounds in the game.
  At each round, the computer will give Apollo two integers and , and Apollo can do exactly one of the following three actions.
  Apollo can do nothing.
  If integer has not been selected in all previous rounds, Apollo can select integer .
  If integer has not been selected in all previous rounds, Apollo can select integer .
  Apollo has cracked the game, and he has known all the candidate numbers of each round before the game starts. Now he wants to know the maximum number of integers he can select with the optimal strategy.
  I believe it would be very simple question for you, please help Apollo solve this question.

输入描述

  The first line is an integer , which is the number of test cases.
  Each test case begins with a line containing a positive integer , indicating the number of rounds in this game.
  Then lines follow. The -th line contains two integers and , indicating that two integers of the -th round.

输出描述

  For each test case, output one line containing , where is the test case number and is the answer.

示例1

输入

2
6
1 2
2 3
3 4
1 4
1 3
2 4
5
1 2
1 2
1 3
2 3
5 6

输出

Case #1: 4
Case #2: 4

分析

  考虑用网络最大流解决。
   和 组成一个二元组，每个二元组至多只能选取其中的一个数字；为了体现这种限制，可以设置 个点，编号为 ，第 个点有两条边分别连向二元组 的两个数，容量为 。每个数字至多被选取一次，将所因此要将所有二元组的数据离散化后，得到 个不同的数字，设为 个点，编号为 ；接着，将代表二元组的 个点向对应的两个数连边。源点向 个表示二元组的点连边，容量为 ； 个表示数据的点向 汇点连边，容量为 。
  按照上述方式建图，满足：每次至多选 中的一个数字，已选的数字不会再选，网络最大流即为答案。由于边的容量为 ，因此当一条边在增广路上时，这条边的容量就被修改为 ；且按照图的结构，残量网络的层数较少；基于以上，虽然 算法的最坏时间复杂度为 （ 为点数， 为边数），但是远远达不到这一上限，在 的时限内是可以通过的。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第八场） Problem I
Date: 9/1/2020
Description: Maximum Flow
*******************************************************************/
#include<iostream>
#include<queue>
#include<unordered_map>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100006;
const int inf=0x3f3f3f3f;
int C,_;
int cnt;
unordered_map<int,int>X;
struct E
{
    int to;
    int cap;
    int Next;
}edge[N*22];
int head[N<<2],tot;
int s,t;//源点 汇点
int depth[N<<2];
int a[N],b[N];
int n;
inline void add_edge(int,int,int);
bool bfs();
int dfs(int,int);
int Dinic();
int main(){
    //s=0 源点
    //1~n 每个二元组 限制流出为1
    //n+1~n+cnt 各个数字
    //t=n+cnt+1 汇点
    for(cin>>_;_;_--){
        scanf("%d",&n);
        int i;
        for(i=1;i<=n;i++){
            scanf("%d%d",a+i,b+i);
        }
        cnt=0;
        X.clear();
        //离散化
        for(i=1;i<=n;i++){
            if(!X.count(a[i])){
                X[a[i]]=++cnt;
            }
            if(!X.count(b[i])){
                X[b[i]]=++cnt;
            }
        }
        //建图
        s=0;
        t=n+cnt+1;
        tot=1;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++){
            //源点流向n个二元组
            add_edge(s,i,1);
        }
        for(i=1;i<=n;i++){
            //每个二元组两个点
            add_edge(i,X[a[i]]+n,1);
            add_edge(i,X[b[i]]+n,1);
        }
        for(i=1;i<=cnt;i++){
            //所有数字连向汇点
            add_edge(i+n,t,1);
        }
        printf("Case #%d: %d\n",++C,Dinic());
    }
    return 0;
}
inline void add_edge(int u,int v,int cap){
    tot++;
    edge[tot].to=v;
    edge[tot].cap=cap;
    edge[tot].Next=head[u];
    head[u]=tot;
    //建立反边
    tot++;
    edge[tot].to=u;
    edge[tot].cap=0;
    edge[tot].Next=head[v];
    head[v]=tot;
}
bool bfs(){
    memset(depth,0,sizeof(depth));
    queue<int>q;
    q.push(s);
    depth[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(register int i=head[x];~i;i=edge[i].Next){
            int y=edge[i].to;
            //残量网络上构建分层图
            if(edge[i].cap&&!depth[y]){
                q.push(y);
                depth[y]=depth[x]+1;
                if(y==t) return 1;//汇点可达
            }
        }
    }
    return 0;
}
int dfs(int x,int flow){//当前节点 当前流量
    //dfs 返回残量网络上可增广的流量
    if(x==t){
        return flow;
    }
    int rest=flow;//rest 剩余流量
    int temp;
    for(register int i=head[x];~i&&rest;i=edge[i].Next){
        int y=edge[i].to;
        if(edge[i].cap&&depth[y]==depth[x]+1){
            temp=dfs(y,min(rest,edge[i].cap));
            if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
            edge[i].cap-=temp;
            edge[i^1].cap+=temp;
            rest-=temp;
        }
    }
    return flow-rest;
}
int Dinic(){
    int maxflow=0;
    while(bfs()){
        maxflow+=dfs(s,inf);
    }
    return maxflow;
}