fork download
copy 
  1. //Bismillahir Rahmanir Rahim
  2. //Shariful Islam(1804011)
  3. //Chittagong University of Engineering & Technology
  4. #include<bits/stdc++.h>
  5. #define pb push_back
  6. #define fin(i,arr,n) for(i=0;i<n;i++)cin>>arr[i]
  7. #define fout(i,arr,n) for(i=0;i<n;i++)cout<<arr[i]<<" "
  8. #define inf 9223372036854775807
  9. #define vi vector<ll>
  10. #define init ll m,a,i,b,j,k,x,y,z,tc,u,v,w
  11. #define f(i,n) for(i=0;i<n;i++)
  12. #define mem(a,x) memset(a,x,sizeof(a))
  13. #define sortt(v)  sort(v.begin(),v.end())
  14. #define sitr(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
  15. #define pr pair<ll,ll>
  16. #define pi acos(-1.00)
  17. #define mod 1000000007
  18. #define yes cout<<"YES"<<endl
  19. #define no cout<<"NO"<<endl
  20. #define tr(exp)  exp?yes:no
  21. #define flush fflush(stdout)
  22. using namespace std;
  23. typedef long long ll;
  24. ll dist[205],visit[205],parent[205],n,s,t,cost=0,flow=0,weight[205][205],adj[205][205];
  25. ll dijkstra()
  26. {   ll i;
  27.     for(i=0;i<=n+1;i++)
  28.     {
  29.         dist[i]=inf;visit[i]=0;
  30.     }
  31.     dist[s]=0;parent[s]=-1;
  32.     while(1)
  33.     {
  34.        ll u,mn=inf,flag=0;
  35.        for(i=0;i<=n+1;i++)
  36.        {
  37.            if(visit[i]==0&&dist[i]<mn)
  38.            {
  39.                mn=dist[i];
  40.                u=i;
  41.                flag=1;
  42.            }
  43.        }
  44.        if(!flag) break; visit[u]=1;
  45.        for(i=0;i<=n+1;i++)
  46.        {
  47.           if(adj[u][i]>0&&dist[i]>weight[u][i]+dist[u])
  48.           {
  49.               dist[i]=weight[u][i]+dist[u];
  50.               parent[i]=u;
  51.           }
  52.        }
  53.  
  54.     }
  55.     if(dist[t]!=inf)
  56.     {
  57.         ll v=t;
  58.         while(1)
  59.         {
  60.             if(parent[v]==-1) break;
  61.             ll u=parent[v];
  62.             adj[u][v]-=1;
  63.             adj[v][u]+=1;
  64.             v=parent[v];
  65.  
  66.         }
  67.         cost+=dist[t];
  68.         flow++;
  69.         return 1;
  70.     }
  71.     return 0;
  72. }
  73.  
  74. int main()
  75. {   ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
  76.       //freopen("read.txt","r",stdin);
  77.       //freopen("write.txt","w",stdout);
  78.       init;
  79.       mem(adj,0);cost=0;flow=0;mem(weight,0);
  80.       cin>>a>>b>>k;
  81.       s=0;t=a+b+1;n=a+b;
  82.       f(i,k)
  83.       {
  84.           cin>>u>>v>>w;
  85.           adj[u][v]=1;
  86.           weight[u][v]=w;
  87.           weight[v][u]=-w;
  88.  
  89.       }
  90.       for(i=1;i<=a;i++) adj[0][i]=1;
  91.       for(i=a+1;i<=a+b;i++) adj[i][t]=1;
  92.  
  93.       while(dijkstra()){};
  94.  
  95.       cout<<"flow: "<<flow<<endl<<"cost: "<<cost<<endl;
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104. }
  105.  
  106.  
  107.  
  108.  
Success #stdin #stdout 0s 5548KB
comments (?)
stdin
copy 
2 1 2
1 3 3
2 3 4
stdout
copy 
flow: 1
cost: 3
https://ideone.com/iP5Kp1
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!