knightL

1421

Oct 18th, 2011
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <iostream>
  6. #include <string>
  7. using namespace std;
  8. #define STR_BUFFER_SIZE 100000
  9. #define INF 1000000000
  10. typedef long long ll;
  11. typedef unsigned ui;
  12.  
  13. int next_int()
  14. {int t; scanf("%d",&t); return t;}
  15. double next_double()
  16. {double t; scanf("%lf",&t); return t;}
  17. ll next_long()
  18. {ll t; scanf("%lld",&t); return t;}
  19. string next_string()
  20. {char buffer[STR_BUFFER_SIZE]; scanf("%s",buffer); return string(buffer);}
  21.  
  22. int v[202][202];
  23. bool used[202];
  24. int s=0, t,n;
  25.  
  26. bool dfs(int s,int t ,int c)
  27. {
  28.     if(used[s]) return false;
  29.     if(s==t) return true;
  30.     used[s]=true;
  31.     for(int i=0;i<=t;i++)
  32.     {
  33.         if(v[s][i]>=c&&dfs(i,t,c))
  34.         {
  35.             v[s][i]-=c;
  36.             v[i][s]+=c;
  37.             return true;
  38.         }
  39.     }
  40.     return false;
  41. }
  42.  
  43. int main()
  44. {
  45.     n=next_int();
  46.     int sum1=0,sum2=0;
  47.     t=2*n+1;
  48.     for(int i=1;i<=n;i++)
  49.         sum1+=(v[s][i]=next_int());
  50.     for(int i=1;i<=n;i++)
  51.         sum2+=(v[i+n][t]=next_int());
  52.     if(sum1==sum2)
  53.     {
  54.         for(int i=1;i<=n;i++)
  55.             for(int j=1;j<=n;j++)
  56.                 v[i][j+n]=INF;
  57.         int flow=0;
  58.         int c=INF;
  59.         while(c>0)
  60.         {
  61.             memset(used,0,sizeof(used));
  62.             if(dfs(s,t,c))
  63.                 flow+=c;
  64.             else
  65.                 c>>=1;
  66.         }
  67.         if(flow==sum1)
  68.         {
  69.             printf("YES\n");
  70.             for(int i=1;i<=n;i++)
  71.             {
  72.                 for(int j=1;j<=n;j++)
  73.                     printf("%d ",v[j+n][i]);
  74.                 puts("");
  75.             }
  76.             return 0;
  77.         }
  78.     }
  79.     printf("NO\n");
  80.     return 0;
  81. }
  82.  
  83.  
Advertisement
Add Comment
Please, Sign In to add comment