fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<memory.h>
  5. #include<vector>
  6. #include<stack>
  7. #include<queue>
  8. #include<cassert>
  9. #include<cstdlib>
  10. #include<cmath>
  11. #include<map>
  12. #include<utility>
  13. #include<cstring>
  14.  
  15. #define DEBUG(x) cout<<#x<<"= "<<x<<endl
  16. #define DEBUGARR(x,i,f) for(int iter = i; iter <= f; ++iter) printf("%s[%d]=%d\n",#x, iter, x[iter])
  17. #define MAX(a,b) ((a)>(b))? (a):(b)
  18. #define MAX3(a,b,c) MAX(a,MAX(b,c))
  19. #define MIN(a,b) ((a)<(b))? (a):(b)
  20. #define MIN3(a,b,c) MIN(a,MIN(b,c))
  21. #define bit(n,i) (n&(1<<(i-1)))
  22. #define setbit(n,i) n |= (1<<(i-1))
  23. #define inf (1<<30)
  24. #define SETZERO(x) memset( x, 0, sizeof(x))
  25. #define SETMIN1(x) memset( x, -1, sizeof(x))
  26. #define CLEAR(x) while(!x.empty()) x.pop();
  27. #define FOR(i,in,fin) for( i = (in); i <= (fin); ++i)
  28. #define FORL(i,in,fin) for( i = (in); i < (fin); ++i)
  29. #define FORD(i,in,fin) for( i = (in); i >= (fin); --i)
  30. #define INC(a,b,c) ((a)<=(b) && (b)<=(c))
  31. #define pb push_back
  32. #define si(x) scanf("%d",&x)
  33. #define pi(x) printf("%d\n",x)
  34. #define sll(x) scanf("%lld",&x)
  35. #define pll(x) printf("%lld\n",x)
  36. #define sortv(v) sort(v.begin(),v.end())
  37. #define sortar(a,i,n) sort(a+i,a+i+n)
  38. #define findmp(mp,x) (mp.find(x)!=mp.end())
  39. typedef long long ill;
  40. using namespace std;
  41. typedef pair <int,int> pii;
  42. const int mod = 1000000007;
  43. //code begins here
  44. map <int,int> mp[11];
  45. vector<int> adj[600];
  46. int cap[600][600];
  47. int n,m,nodes;
  48. void build_graph()
  49. {
  50.     int i,j;
  51.     nodes=0;
  52.     vector <pii> in,out;
  53.     FOR(i,1,n)
  54.     {
  55.         int src = ++nodes;
  56.         int sink = ++nodes;
  57.         if(i>1)
  58.         {
  59.             cap[sink][src]=1000000;
  60.             adj[sink].push_back(src);
  61.         }
  62.         FOR(j,1,m)
  63.         {
  64.             nodes++;
  65.             if(mp[i].count(j))
  66.             {
  67.                 if(mp[i][j]==1)
  68.                     continue;
  69.                 out.pb(make_pair(nodes,j));
  70.                 adj[src].push_back(nodes);
  71.                 cap[src][nodes] = mp[i][j]-1;
  72.             }
  73.             else
  74.             {
  75.                 in.pb(make_pair(nodes,j));
  76.                 adj[nodes].push_back(sink);
  77.                 cap[nodes][sink]=1;
  78.             }
  79.         }
  80.     }
  81.     FORL(i,0,out.size())
  82.     {
  83.         FORL(j,0,in.size())
  84.         {
  85.             if(out[i].second==in[j].second)
  86.             {
  87.                 adj[out[i].first].push_back(in[j].first);
  88.                 cap[out[i].first][in[j].first] = 1;
  89.             }
  90.         }
  91.     }
  92. }
  93. int bfs()
  94. {
  95.     queue <int> Q;
  96.     int vis[600] = {}, from[600]={},i;
  97.     Q.push(1);
  98.     vis[1] = 1;
  99.     int flag = 1;
  100.     while( !Q.empty() && flag)
  101.     {
  102.         int x = Q.front();
  103.         Q.pop();
  104.         for( i = 0; i < adj[x].size(); i++)
  105.         {
  106.             int y = adj[x][i];
  107.             if( !vis[y] && cap[x][y] > 0)
  108.             {
  109.                 Q.push(y);
  110.                 vis[y] = 1;
  111.                 from[y] = x;
  112.                 if( y == 2)//N is the sink
  113.                 {
  114.                     flag = 0;
  115.                     break;
  116.                 }
  117.             }
  118.         }
  119.     }
  120.     int where = 2;
  121.     int path_cap = 1000000;
  122.     while( from[where])
  123.     {
  124.         int prev = from[where];
  125.         path_cap = min( path_cap, cap[prev][where]);
  126.         where = prev;
  127.     }
  128.     where = 2;
  129.     while( from[where])
  130.     {
  131.         int prev = from[where];
  132.         cap[prev][where] -= path_cap;
  133.         where = prev;
  134.     }
  135.     if( path_cap == 1000000)
  136.     {
  137.         return 0;
  138.     }
  139.     else
  140.     {
  141.         return path_cap;
  142.     }
  143. }
  144. int max_flow()
  145. {
  146.     int result = 0;
  147.     while(1)
  148.     {
  149.         int path_capacity = bfs();
  150.         if(!path_capacity)
  151.         {
  152.             return result;
  153.         }
  154.         else
  155.         {
  156.             result += path_capacity;
  157.         }
  158.     }
  159. }
  160. int main()
  161. {
  162.     #ifndef ONLINE_JUDGE
  163.         freopen("a.in","r",stdin);
  164.     #endif // ONLINE_JUDGE
  165.     int t,tc;
  166.     scanf("%d",&t);
  167.     FOR(tc,1,t)
  168.     {
  169.         int k,i,j;
  170.         SETZERO(cap);
  171.         si(n);si(m);
  172.         FOR(i,1,n)
  173.         {
  174.             mp[i].clear();
  175.             si(k);
  176.             FOR(j,1,k)
  177.             {
  178.                 int x;
  179.                 si(x);
  180.                 mp[i][x]++;
  181.             }
  182.         }
  183.         build_graph();
  184.         assert(nodes<600);
  185.         printf("Case #%d: %d\n",tc,max_flow()+mp[1].size());
  186.         FOR(i,0,nodes)
  187.         {
  188.             adj[i].clear();
  189.         }
  190.     }
  191. }
  192.  
  193.  
  194.  
Success #stdin #stdout 0s 4852KB
comments (?)
stdin
copy 
2
2 5
6 1 1 1 1 1 1
3 1 2 2
3 5
4 1 2 1 1
3 2 2 2
5 1 3 4 4 3
stdout
copy 
Case #1: 1
Case #2: 3
https://ideone.com/f5iN3M
language:
C++ (gcc 8.3)
created:
10 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!