fork download 
  1. #include <ctime>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <cassert>
  6. #include <cmath>
  7. #include <cctype>
  8. #include <algorithm>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <string>
  13. #include <iostream>
  14. #include <sstream>
  15. #include <functional>
  16. using namespace std;
  17. char mat[111][111];
  18. int n,deg[111],uk[111][111],now[111],tot;
  19. int pa[111],num[111];
  20. int dist[111];
  21. int adj[111][111];
  22. int vec[111][111],num_vec[111];
  23. int vs[111],times,u;
  24. int spfa()
  25. {
  26.     int id,ip,i,j,s,p,q;
  27.     for(i=0;i<=n;i++)
  28.          num_vec[i]=0;
  29.     for(i=0;i<n;i++)
  30.     {
  31.         dist[i]=now[i]+deg[i]; 
  32.         pa[i]=-1;
  33.         vec[now[i]+deg[i]][num_vec[now[i]+deg[i]]++]=i;
  34.     } 
  35.     times++;
  36.     while(true)
  37.     {
  38.         for(;u>=0;u--)
  39.         {
  40.             while(num_vec[u]>0)
  41.             {
  42.                 id=vec[u][num_vec[u]-1];
  43.                 if(vs[id]!=times)
  44.                    break;
  45.                 num_vec[u]--;
  46.             }
  47.             if(num_vec[u]>0)
  48.                 break;
  49.         }
  50.         if(u<0)
  51.            return -1;
  52.         num_vec[u]--;
  53.         vs[id]=times;
  54.         for(j=0;j<num[id];j++)
  55.         {
  56.             ip=adj[id][j];
  57.             if(dist[ip]<dist[id]&&uk[id][ip]==0)
  58.             {
  59.                 dist[ip]=dist[id];
  60.                 pa[ip]=id;
  61.                 if(dist[ip]>=now[ip]+deg[ip]+2)
  62.                     return ip;
  63.                 vec[dist[ip]][num_vec[dist[ip]]++]=ip;
  64.             }
  65.         }
  66.     }
  67. }
  68. int main()
  69. {
  70.     int i,j,s,p,q,id,ip,dk;
  71.     while(scanf("%d",&n)==1)
  72.     {
  73.         tot=n*(n-1)*(n-2)/6;
  74.         for(i=0;i<n;i++)
  75.             deg[i]=now[i]=num[i]=0;
  76.         for(i=0;i<n;i++)
  77.           for(j=0;j<n;j++)
  78.           {
  79.              mat[i][j]=getchar();
  80.              while(mat[i][j]<'0'||mat[i][j]>'9')
  81.                  mat[i][j]=getchar();
  82.               if(i==j)
  83.                  continue;
  84.               if(mat[i][j]=='0')
  85.                  deg[i]++;
  86.               else if(mat[i][j]=='2')
  87.               {
  88.                  if(i<j)
  89.                  {
  90.                       uk[i][j]=rand()%2;
  91.                       uk[j][i]=1-uk[i][j]; 
  92.                       if(uk[i][j]==0) 
  93.                          now[i]++;
  94.                       else
  95.                          now[j]++;
  96.                  }
  97.                  adj[i][num[i]++]=j;
  98.               }
  99.           }
  100.         u=n;
  101.         while(true)
  102.         {
  103.              ip=spfa();
  104.              if(ip<0)
  105.                 break;
  106.              now[ip]++;
  107.              while(pa[ip]>=0)
  108.              {
  109.                  uk[pa[ip]][ip]=1;
  110.                  uk[ip][pa[ip]]=0;
  111.                  ip=pa[ip];
  112.              }
  113.              now[ip]--;
  114.         }
  115.         for(i=0;i<n;i++)
  116.         {
  117.             dk=deg[i]+now[i];
  118.             tot-=dk*(dk-1)/2;
  119.         }
  120.         printf("%d\n",tot);
  121.         for(i=0;i<n;i++)
  122.         {
  123.            for(j=0;j<n;j++)
  124.            {
  125.                if(mat[i][j]=='2')
  126.                    mat[i][j]=uk[i][j]+'0';
  127.                putchar(mat[i][j]);
  128.                putchar(' ');
  129.            }
  130.            printf("\n");
  131.         }
  132.     }
  133.     return 0;
  134. }
Success #stdin #stdout 0s 16224KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/tN2Gdb
language:
C++ (gcc 8.3)
created:
7 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!