poj 1273 网络流

短命女 2024-02-17 19:24 180阅读 0赞 
  1. #include<iostream>
  2. #include<queue>
  3. #include<cstring>
  4. #include<cstdio>
  5. using namespace std;
  6. int res[202][202],minn,n,m,pre[202],a[202];
  7. bool bfs(){
  8. queue<int>q;
  9. q.push(1);
  10. int k;
  11. memset(a,0,sizeof(a));
  12. a[1]=0x3f3f3f3f;
  13. while(!q.empty()){
  14.     k=q.front();
  15.     if(k==m) return 1;
  16.     q.pop();
  17.     for(int i=1;i<=m;i++){
  18.       if(!a[i]&&res[k][i]){
  19.         q.push(i);
  20.         pre[i]=k;
  21.         a[i]=min(a[k],res[k][i]);
  22.       }
  23.     }
  24. }
  25. return 0;
  26. }
  27. int maxflow(){
  28.     int ans=0;
  29. while(bfs()){
  30.         ans+=a[m];
  31.     int k=m;
  32.     while(k!=1){
  33.         res[pre[k]][k]-=a[m];
  34.         res[k][pre[k]]+=a[m];
  35.         k=pre[k];
  36.     }
  37. }
  38. return ans;
  39. }
  40. int main(){
  41.    // freopen("1.txt","r",stdin);
  42. int t1,t2,t3;
  43. while(cin>>n>>m){
  44.         memset(res,0,sizeof(res));
  45. for(int i=1;i<=n;i++){
  46.     cin>>t1>>t2>>t3;
  47.     res[t1][t2]+=t3;
  48. }
  49. cout<<maxflow()<<endl;
  50. }
  51. }

发表评论

表情：
评论列表 （有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

    相关 poj 2455 二分+最大流

    这个因为点少用邻接矩阵做的。 题意：求由1到n的t条不重复路径中最大边权值的最小值。 思路：先对边权进行排序，然后二分边权值，建图求从1到n的最大流，当最大流为t时便求出答

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 296 阅读