首页 > 代码库 > hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)
hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)
题目链接:http://hihocoder.com/problemset/problem/1394
代码:
#include<bits/stdc++.h>using namespace std;const int N=505*2+10,M=20005,INF=0x3f3f3f3f;int n,m;int c[N][N],pre[N];int s,t;int bfs(){ memset(pre,0,sizeof(pre)); queue<int>q; q.push(s); pre[s]=1; while(!q.empty()) { int tmp=q.front(); q.pop(); for(int i=s+1;i<=t;i++) { if(pre[i]==0&&c[tmp][i]>0) { pre[i]=pre[tmp]+1; q.push(i); } } } if(pre[t]) return 1; return 0;}int dfs(int x,int f){ if(x==t||f==0) return f; int k=0,ans=0; for(int i=1;i<=t;i++) { if(pre[i]==pre[x]+1&&c[x][i]) { k=dfs(i,min(f,c[x][i])); if(k) { ans+=k,f-=k; c[x][i]-=k; c[i][x]+=k; } if(f==0) break; } } return ans;}int maxflow(){ int ans=0; while(bfs()) { ans+=dfs(s,INF); } return n-ans;}int main(){ int u,v; memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); s=0,t=n+1+n; for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); c[u][v+n]=1; } for(int i=1;i<=n;i++) { c[0][i]=1; c[i+n][n+1+n]=1; } printf("%d\n",maxflow());}
就是这个。我感觉我已经把原来在我心中的模板改成乱七八糟的了。、
说好听点是融合了,然而我总感觉会忘记一些东西。。。可怕
这题就是用网络流实现二分图匹配。
hihoCoder 1394 : 网络流四·最小路径覆盖 (网络流学习#4 记录)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。