[UVALive 3231]Fair Share

Description
You are given $N$N processors and $M$M jobs to be processed. Two processors are specified to each job. To process the job, the job should be allocated to and executed on one of the two processors for one unit of time. If $K$K jobs are allocated to a processor, then it takes $K$K units of time for the processor to complete the jobs. To complete all the jobs as early as possible, you should allocate the $M$M jobs to the $N$N processors as fair as possible. Precisely speaking, you should minimize the maximum number of jobs allocated to each processor over all processors. The quantity, minimum number of jobs, is called fair share.

For example, you are given 5 processors and 6 jobs. Each job can be allocated to one of the two processors as shown in the table below. Job 1 can be allocated to processors 1 or 2, and job 2 can be allocated to processors 2 or 3, etc. If you allocate job 1 to processor 1, job 2 to processor 2, job 3 to processor 3, job 4 to processor 4, job 5 to processor 5, and job 6 to processor 1, then you have at most two jobs allocated to each processor. Since there are more jobs than processors in this example, some processors necessarily have at least two jobs, and thus the fair share is two.

Given $N$N processors, $M$M jobs, and the sets of two processors to which the jobs can be allocated, you are to write a program that finds the fair share. Processors are numbered from 1 to $N$N and jobs are numbered from 1 to $M$M . It is assumed that the sets of two processors to which the jobs can be allocated are distinct over all jobs.
That is, if a job $J_1$J1​ can be allocated to processors $P_1$P1​ or $P_2$P2​, and a job $J_2$J2​ which is different from $J_1$J1​ can be allocated to processors $P_3$P3​ or $P_4$P4​, then {$P_1, P_2$P1​,P2​}$\ne$​={$P_3, P_4$P3​,P4​}.

Input

The input consists of $T$T test cases. The number of test cases $T$T is given in the first line of the input file. Each test case begins with a line containing an integer $N, 1 \le N \le 1, 000$N,1≤N≤1,000, that represents the number of processors in the test case. It is followed by a line containing an integer $M, 1 \le M \le 10, 000,$M,1≤M≤10,000, that represents the number of jobs. In the following $M$M lines, $K$K-th line contains two distinct integers representing processors to which job $K$K can be allocated, $1 \le K \le M$1≤K≤M. The integers given in a line are separated by a space. After that, the remaining test cases are listed in the same manner as the above.

Output

Print exactly one line for each test case. The line should contain the fair share for that test case.
The following shows sample input and output for three test cases.

**Sample Input **

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

Sample Output

2  
1 
2

题意
有$m$m个任务$n$n个处理器，一个任务只能在两个指定处理器之一上运行，问怎样分配任务使得任务最多的处理器的任务尽量少。

思路
最大流+二分答案，将每个任务与对应的处理器连容量为1的边，将源点向每个任务连容量为1的边，然后将处理器向汇点连边，二分答案，每次改变处理器向汇点连边的容量。这样总共需要跑$logM$logM次网络流。

AC代码

//luogu P2756 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=1e5+5;
const int inf=0x3f3f3f3f;
struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol;
int head[maxn];int Q[maxn];
int dep[maxn],cur[maxn],sta[maxn];
int m,n,z,s,t;
void init()
{
	tol=2;
	memset(head,-1,sizeof(head));
}
void AddEdge(int u,int v,int w,int rw=0)
{
	edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
	edge[tol].nxt=head[u];head[u]=tol++;
	edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
	edge[tol].nxt=head[v];head[v]=tol++;
}
bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if(edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if(v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}
int dinic(int s,int t,int n){
	int maxflow=0,u;
	while(bfs(s,t,n)){
		u=s;
		int tail=0;
		for(int i=0;i<n;i++) cur[i]=head[i];
		while(cur[s]!=-1){
			if(u==t){
				int tp=inf;
				for(int i=tail-1;i>=0;i--){
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				}
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if(edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else {
 				while(u!=s&&cur[u]==-1)u=edge[sta[--tail]^1].to;
                      				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}
int modify(int c)
{
	for(int i=head[t];i!=-1;i=edge[i].nxt)
	{
		edge[i^1].cap=c;
	}
	for(int i=1;i<=tol;i++)edge[i].flow=0;
	return 0;
}
int main()
{
	scanf("%d",&z);
	while(z--)
	{
		scanf("%d%d",&n,&m);
		int u,v;
		init();
		s=0,t=n+m+1;
		for(int i=1;i<=m;i++) AddEdge(s,i,1);
		for(int i=m+1;i<=m+n;i++) AddEdge(i,t,m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			AddEdge(i,m+u,1);
			AddEdge(i,m+v,1);
		}
		int l=1,r=m;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			modify(mid);
			if(dinic(s,t,n+m+2)<m)l=mid+1;else r=mid-1;
		}
		printf("%d\n",r+1);
	}
	return 0;
}