1 条题解
-
0
#include<bits/stdc++.h> #define N 510 #define M 20100 #define INF 0x3f3f3f3f using namespace std; int head[N<<1]; int dep[N<<1]; struct node { int from,to,val,next; }edge[M]; int cnt,S,T,n,k; void init() { memset(head,-1,sizeof(head)); } void edgeadd(int from,int to,int val) { edge[cnt].from=from,edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } int bfs(int s,int e) { memset(dep,0,sizeof(dep)); queue<int>q; q.push(s); dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); if(u==e)return 1; for(int i=head[u];i!=-1;i=edge[i].next) { int to=edge[i].to; if(dep[to]==0&&edge[i].val!=0) { dep[to]=dep[u]+1; q.push(to); } } } return 0; } int dfs(int s,int max_vale) { int ret=0,tmp; if(s==n*2+1)return max_vale; for(int i=head[s];i!=-1;i=edge[i].next) { int to=edge[i].to; if(dep[to]!=dep[s]+1||edge[i].val==0)continue; tmp=dfs(to,min(max_vale-ret,edge[i].val)); edge[i].val-=tmp; edge[i^1].val+=tmp; ret+=tmp; if(ret==max_vale)return max_vale; } return ret; } int dinic() { int ret=0; while(bfs(S,T)) { while(int t=dfs(S,INF)) { ret+=t; } } return ret; } int main() { init(); scanf("%d%d",&n,&k); S=0,T=n*2+1; for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); edgeadd(x,y+n,1); edgeadd(y+n,x,0); } for(int i=1;i<=n;i++) { edgeadd(S,i,1); edgeadd(i,S,0); edgeadd(i+n,T,1); edgeadd(T,i+n,0); } printf("%d\n",dinic()); return 0; }
- 1
信息
- ID
- 1693
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 4
- 已通过
- 4
- 上传者