fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define tag "spoj"
  4. #define maxn 207
  5. #define maxc 40007
  6. #define oo 1000000007
  7. #define mid ((l+r)>>1)
  8. #define meset(a,x) memset(a,x,sizeof(a))
  9. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  10. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  11. int n;
  12. int d[maxn];
  13. int c[maxn][maxn];
  14. int mx[maxn],my[maxn];
  15. int bx[maxn],by[maxn];
  16. int fx[maxn],fy[maxn];
  17. #define residual(i,j) (fx[i]+c[i][j]-fy[j])
  18.  
  19. void augmenting(int v)
  20. {
  21.     int u,k;
  22.     while(v>0)
  23.     {
  24.         k=mx[u=by[v]];
  25.         mx[u]=v;
  26.         my[v]=u;
  27.         v=k;
  28.     }
  29. }
  30.  
  31. bool augment(int u)
  32. {
  33.     meset(bx,0);meset(by,0);
  34.     fill(d+1,d+n+1,maxc);
  35.  
  36.     queue<int> Q;
  37.     Q.push(u),bx[u]=1;
  38.  
  39.     while(Q.size())
  40.     {
  41.         u=Q.front(),Q.pop();
  42.  
  43.         for(int v=1;v<=n;v++)
  44.         if(by[v]) continue;
  45.         else if(residual(u,v)==0)
  46.         {
  47.             d[v]=maxc;
  48.             by[v]=u;
  49.  
  50.             if(my[v]==0)
  51.             {
  52.                 augmenting(v);
  53.                 return true;
  54.             }
  55.  
  56.             Q.push(my[v]);
  57.             bx[my[v]]=1;
  58.         }
  59.         else d[v]=min(d[v],residual(u,v));
  60.     }
  61.  
  62.     return false;
  63. }
  64.  
  65. void repair()
  66. {
  67.     int dt=*min_element(d+1,d+n+1);
  68.     for(int u=1;u<=n;u++) if(!bx[u]) fx[u]+=dt;
  69.     for(int v=1;v<=n;v++) if(!by[v]) fy[v]+=dt;
  70. }
  71. int main()
  72. {
  73.     #ifdef dmdd
  74.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  75.     #endif // dmdd
  76.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  77.  
  78.     cin>>n;
  79.  
  80.     meset(c,127);
  81.  
  82.     int x,y,z;
  83.     while(cin>>x>>y>>z) c[x][y]=z;
  84.  
  85.     for(int u=1;u<=n;u++)
  86.         while(!augment(u))
  87.             repair();
  88.  
  89.     long long ans=0;
  90.     for(int u=1;u<=n;u++) ans+=c[u][mx[u]];
  91.  
  92.     cout<<ans<<"\n";
  93.     for(int u=1;u<=n;u++) cout<<u<<" "<<mx[u]<<"\n";
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
4
1 1 0
1 2 0
2 1 0
2 4 2
3 2 1
3 3 0
4 3 0
4 4 9
stdout
copy 
3
1 1
2 4
3 2
4 3
https://ideone.com/BKu17d
language:
C++14 (gcc 8.3)
created:
6 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!