[POI2005]Kos-Dicing【二分答案+最大流】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1532
【算法分析】
二分答案然后，将比赛分配给选手，判定能不能分完。
这个用最大流实现。
【其它】sap被卡。HLPP被卡。。。于是dinic。。。
于是你可以见识到什么叫卡过。。。
34 30276 edward_mj 3164K 4772MS G++ 2.39K 2010-06-16 01:39:26 【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
const int N=20005;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}*ls[N],*cur[N],*fa[N];
int n,m,vs,vt,Flow;
int d[N],lx[N],ly[N],v[N],Q[N];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&lx[i],&ly[i]);
vs=0; vt=n+m+1;
}

inline void addedge(int x,int y,int c){
edge *p=(edge*)malloc(sizeof(edge));
edge *q=(edge*)malloc(sizeof(edge));
p->x=x; p->y=y; p->c=c; p->next=ls[x]; ls[x]=p; p->op=q;
q->x=y; q->y=x; q->c=0; q->next=ls[y]; ls[y]=q; q->op=p;
}

bool bfs(){
for (int i=vs;i<=vt;i++){
d[i]=INF;
v[i]=0;
cur[i]=ls[i];
}
d[vs]=1; Q[1]=vs;
for (int st=1,ed=1;st<=ed;st++)
for (edge *t=ls[Q[st]];t;t=t->next)
if (t->c && d[t->y]==INF){
d[t->y]=d[t->x]+1;
Q[++ed]=t->y;
if (t->y==vt) return true;
}
return false;
}

void change(){
int nf=INF;
for (int i=vt;i!=vs;i=fa[i]->x)
if (fa[i]->c for (int i=vt;i!=vs;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
Flow+=nf;
}

void dinic(){
int i;
while (bfs()){
i=vs;
while (cur[vs]){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->x]+1==d[t->y] && !v[t->y]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==vt){
change();
i=vs;
}
}else{
v[i]=1;
if (i!=vs) i=fa[i]->x;
}
}
}
}

bool Can(int Limit){
for (int i=vs;i<=vt;i++)
while (ls[i]){
edge*t=ls[i];
ls[i]=t->next;
free(t);
}
for (int i=1;i<=m;i++){
addedge(vs,i,1);
addedge(i,m+lx[i],1);
addedge(i,m+ly[i],1);
}
for (int i=1;i<=n;i++) addedge(m+i,vt,Limit);
Flow=0;
dinic();
if (Flow==m) return true;
return false;
}

void solve(){
int l=m/n,r=m,mid;
while (l mid=(l+r)/2;
if (Can(mid)) r=mid;
else l=mid+1;
}
printf("%dn",l);
}

int main(){
init();
solve();
}