1 条题解
-
1陈烨鑫 (chenyexin) LV 10 @ 2023-6-10 9:33:21
#include<bits/stdc++.h> using namespace std ; const int maxn=110; const int oo=1000000000; typedef struct EDGE{ int u,v; int c,f,next; EDGE (){ u=v=c=f=0; next=-1; } EDGE (int a,int b,int d,int e,int g){ u=a;v=b;c=d;f=e;next=g; } }E; E edge[100*maxn+10]; int len=-1,head[maxn],n,m; int vis[maxn],dis[maxn]; int cur[maxn]; int allp;//总的点个数 int S,T;//源点和汇点的编号 void E_add (int s,int t,int x,int y){ edge[++len]=EDGE (s,t,x,y,head[s]); head[s]=len; } void init (){ cin >>m >>n; int i,j; S=n+1; T=n+2; allp=T; memset (head,-1,sizeof (head)); while (1){ scanf ("%d%d",&i,&j); if (i==-1&&j==-1) break; E_add (i,j,1,0); E_add (j,i,0,0); } for (i=m+1;i<=n;i++) { E_add (i,T,1,0); E_add (T,i,0,0); } for (i=1;i<=m;i++) { E_add (S,i,1,0); E_add (i,S,0,0); } } int bfs (){ memset (vis,0,sizeof(vis)); int q[100*maxn],headx=0,tail=0; int now,i; q[tail++]=S; vis[S]=1; dis[S]=1; while (headx<tail){ now=q[headx++]; for (i=head[now];i!=-1;i=edge[i].next){ if (!vis[edge[i].v]&&edge[i].c>edge[i].f) { q[tail++]=edge[i].v; dis[edge[i].v]=dis[now]+1; vis[edge[i].v]=1; } } } return vis[T]; } int dfs (int x,int fmax){ if (x==T||fmax==0) return fmax; int f,flow=0,&now=cur[x]; for (;now!=-1;now=edge[now].next){ if (dis[edge[now].v]==dis[x]+1&&(f=(dfs (edge[now].v,min(fmax,edge[now].c-edge[now].f))))){ flow+=f; edge[now].f+=f; edge[now^1].f-=f; fmax-=f; if (fmax==0) break; } } return flow; } int dinic (){ int flow=0,i; while (bfs ()){ for (i=1;i<=allp;i++) cur[i]=head[i]; flow+=dfs (S,oo); } return flow; } int main (){ init (); printf ("%d\n",dinic ()); return 0; }
- 1
信息
- ID
- 323
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 24
- 已通过
- 11
- 上传者