题解 P3425 【[POI2005]KOS-Dicing】

【POI补全计划#9 POI2005 KOS】 思维难度算比较简单的一题了 二分后用网络流判定 建图分3部分 1.S->人，流量为二分的mid 2.人->比赛，流量为1（只有参赛选手需要连边） 3.比赛->T，流量为1 输出方案只需要记录每一场比赛的满流边连向那个人就行 **不要忘记初始化** 贴代码 ```cpp #include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAXN=20010,inf=0x3f3f3f3f; struct edge { int v,f; edge *next,*rev; }*h[MAXN],pool[MAXN*5]; const int S=20005,T=20006,SHIFT=10000; int top; inline void addedge(int u,int v,int c) { edge *tmp=&pool[++top];tmp->v=v;tmp->f=c;tmp->next=h[u];h[u]=tmp; edge *pmt=&pool[++top];pmt->v=u;pmt->f=0;pmt->next=h[v];h[v]=pmt; tmp->rev=pmt;pmt->rev=tmp; } int level[MAXN]; queue<int> q; inline bool mklevel() { while(!q.empty())q.pop(); memset(level,-1,sizeof(level)); level[S]=0; q.push(S); while(!q.empty()) { int u=q.front();q.pop(); for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(tmp->f&&level[tmp->v]==-1) { level[tmp->v]=level[u]+1; q.push(tmp->v); } } if(level[T]!=-1)return true; } return false; } int dinic(int u,int minf) { if(u==T)return minf; int totf=0,f; for(edge *tmp=h[u];tmp&&totf<minf;tmp=tmp->next) { if(tmp->f&&level[tmp->v]==level[u]+1) { if(minf-totf<tmp->f)f=dinic(tmp->v,minf-totf); else f=dinic(tmp->v,tmp->f); totf+=f; tmp->f-=f; tmp->rev->f+=f; } } if(!totf)level[u]=-1; return totf; } int n,m,a[MAXN],b[MAXN],ans[MAXN]; inline void getans() { for(int i=1;i<=m;i++) { for(edge *tmp=h[i+SHIFT];tmp;tmp=tmp->next) { if(tmp->v!=T&&tmp->f==1) { if(tmp->v==a[i])ans[i]=1; else ans[i]=0; } } } } int main() { scanf("%d%d",&n,&m); if(!m) { printf("0\n"); return 0; } for(int i=1;i<=m;i++) { scanf("%d%d",&a[i],&b[i]); } int l=1,r=10000; while(l<r) { int mid=(l+r)/2; memset(h,0,sizeof(h)); top=0; for(int i=1;i<=n;i++) { addedge(S,i,mid); } for(int i=1;i<=m;i++) { addedge(a[i],i+SHIFT,1); addedge(b[i],i+SHIFT,1); addedge(i+SHIFT,T,1); } int totf=0; while(mklevel())totf+=dinic(S,inf); if(totf==m) { getans(); r=mid; } else l=mid+1; } printf("%d\n",l); for(int i=1;i<=m;i++) { printf("%d\n",ans[i]); } return 0; } ```