原來網(wǎng)絡(luò)流也能二分，今天終于見識(shí)了。。。
二分+最大流
題目大意：給定n個(gè)人m場(chǎng)比賽，問贏的最多的人最少贏幾場(chǎng)
二分答案，增加源匯點(diǎn)，左邊一排是比賽點(diǎn)，右邊是球員，若有比賽，比賽向倆球員連容量為1的邊
源點(diǎn)向比賽連容量為1的邊，球員向匯點(diǎn)連容量為二分枚舉值的邊，判斷是最大流是否等于比賽個(gè)數(shù)
網(wǎng)絡(luò)流的構(gòu)圖真是個(gè)神奇的東西，我承認(rèn)如果不看網(wǎng)上的解題報(bào)告，我真的很難想到，首先是題意不太明確，剛開始我還以為贏的最多的選手勝利的場(chǎng)次必須是最多的。。。但是從樣例來看，貌似就算每個(gè)人都贏一場(chǎng)也會(huì)有冠軍出現(xiàn)。。。說說我的理解吧，從超級(jí)源點(diǎn)引一條邊至代表每場(chǎng)比賽的節(jié)點(diǎn)，限制每場(chǎng)比賽的勝利者只有一個(gè)人，這個(gè)流量如果在射出到某個(gè)選手的一條邊中，代表這場(chǎng)比賽是他取勝。每個(gè)選手到匯點(diǎn)連一條二分枚舉的邊，就是限制勝利場(chǎng)次的上界，如果最后的最大流等于m,說明這m場(chǎng)比賽的的勝者可以合理的分配，如果不能，說明比賽不能正常進(jìn)行。又可以分析得出，如果某一個(gè)二分值mid滿足要求，那么比他大的值一定也滿足要求。故可二分枚舉答案。（PS:這題的復(fù)雜度應(yīng)該是(10000+10000+2)^2*(m*2+m+n)*log 10000.總覺得要超時(shí)啊。。。難道數(shù)據(jù)弱了？）
int n,m;
struct node2
{
int a,b;
}re[100000];
bool check(int n,int m,int mid)
{
int i;
for(i=0;i<n+m+2;i++)
adj[i]=NULL;
len=0;
int s=n+m;
int t=s+1;
for(i=0;i<m;i++)
insert(s,i,1);
for(i=0;i<n;i++)
insert(m+i,t,mid);
for(i=0;i<m;i++)
{
insert(i,m+re[i].a,1);
insert(i,m+re[i].b,1);
}
return dinic(t+1,s,t)==m;
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf("%d%d",&re[i].a,&re[i].b);
re[i].a--;
re[i].b--;
}
int l=1,r=m;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(n,m,mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}