SHARE
TWEET

SAM I AM - UVa 11419 AC

royalsflush Sep 17th, 2012 117 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. const int MAXV = 2010;
  8. const int MAXE = (2010*2010+2010);
  9. const int inf = 0x3f3f3f3f;
  10.  
  11. int nV, vE;
  12. int n;
  13. int r,c;
  14. int s,t;
  15.  
  16. int lastEdge[MAXV];
  17.  
  18. struct edge {
  19.         int dst,f,c;
  20.         int prev;
  21. };
  22.  
  23. edge ls[MAXE];
  24. int currEdge[MAXV];
  25. queue<int> q;
  26. int d[MAXV];
  27.  
  28. void makeEdge(int src, int dst, int cap) {
  29.         ls[vE].dst=dst, ls[vE].c=cap, ls[vE].f=0;
  30.         ls[vE].prev=lastEdge[src];
  31.         lastEdge[src]=vE++;
  32. }
  33.  
  34. bool bfs() {
  35.         while (!q.empty()) q.pop();
  36.         memset(d,0x3f,sizeof(d));
  37.  
  38.         d[s]=0;
  39.         q.push(s);
  40.  
  41.         for (int i=0; i<nV; i++)
  42.                 currEdge[i]=lastEdge[i];
  43.  
  44.         while (!q.empty()) {
  45.                 int u=q.front();
  46.                 if (u==t)
  47.                         return true;
  48.                 q.pop();
  49.  
  50.                 for (int i=lastEdge[u]; i!=-1; i=ls[i].prev) {
  51.                         int v=ls[i].dst;
  52.  
  53.                         if (ls[i].c-ls[i].f==0) continue;
  54.                         if (d[v]!=inf) continue;
  55.  
  56.                         d[v]=d[u]+1;
  57.                         q.push(v);     
  58.                 }
  59.         }
  60.  
  61.         return false;
  62. }
  63.  
  64. int dfs(int u, int flow) {
  65.         if (u==t) return flow;
  66.  
  67.         for (int& i=currEdge[u]; i!=-1; i=ls[i].prev) {
  68.                 int v=ls[i].dst;
  69.  
  70.                 if (d[v]!=d[u]+1) continue;
  71.                 if (ls[i].c-ls[i].f==0) continue;
  72.  
  73.                 int tmpF = dfs(v,min(ls[i].c-ls[i].f, flow));
  74.        
  75.                 if (tmpF) {
  76.                         ls[i].f+=tmpF;
  77.                         ls[i^1].f-=tmpF;
  78.                         return tmpF;
  79.                 }
  80.         }
  81.  
  82.         return 0;
  83. }
  84.  
  85. int dinic() {
  86.         int maxFlow=0;
  87.  
  88.         while (bfs())
  89.                 while (int flow=dfs(s,inf))
  90.                         maxFlow+=flow;
  91.  
  92.         return maxFlow;
  93. }
  94.  
  95. bool tmark[MAXV];
  96.  
  97. void recDfs(int u) {
  98.         tmark[u]=true;
  99.  
  100.         for (int i=lastEdge[u]; i!=-1; i=ls[i].prev) {
  101.                 if (tmark[ls[i].dst])
  102.                         continue;              
  103.                 if (ls[i].dst>=r+c)
  104.                         continue;
  105.  
  106.                 if (u<r) {
  107.                         if (ls[i].c-ls[i].f>0)
  108.                                 recDfs(ls[i].dst);
  109.                 }
  110.                 else
  111.                         if (ls[i^1].c-ls[i^1].f==0)
  112.                                 recDfs(ls[i].dst);
  113.         }
  114. }
  115.  
  116. bool mark[MAXV];
  117.  
  118. void recover() {
  119.         memset(tmark,0,sizeof(tmark));
  120.         memset(mark,0,sizeof(mark));   
  121.  
  122.         for (int i=lastEdge[s]; i!=-1; i=ls[i].prev)
  123.                 if (ls[i].c-ls[i].f>0)
  124.                         recDfs(ls[i].dst);
  125.  
  126.         for (int i=0; i<r; i++)
  127.                 if (!tmark[i]) mark[i]=true;
  128.         for (int i=0; i<c; i++)
  129.                 if (tmark[i+r]) mark[i+r]=true;
  130. }
  131.  
  132. int main() {
  133.         while (1) {
  134.                 scanf("%d %d %d", &r,&c,&n);
  135.                 if (!r && !c && !n) break;
  136.  
  137.                 memset(lastEdge,-1,sizeof(lastEdge));
  138.  
  139.                 nV=r+c+2, vE=0;
  140.                 s=r+c, t=r+c+1;
  141.  
  142.                 for (int k=0; k<n; k++) {
  143.                         int x,y;
  144.                         scanf("%d %d", &x,&y);
  145.                         x--, y--;
  146.                        
  147.                         makeEdge(x,y+r,1);
  148.                         makeEdge(y+r,x,0);
  149.                 }
  150.  
  151.                 for (int i=0; i<r; i++) {
  152.                         makeEdge(s,i,1);
  153.                         makeEdge(i,s,0);
  154.                 }
  155.  
  156.                 for (int i=0; i<c; i++) {
  157.                         makeEdge(i+r,t,1);
  158.                         makeEdge(t,i+r,0);
  159.                 }
  160.  
  161.                 printf("%d", dinic());
  162.                 recover();
  163.                
  164.                 for (int i=0; i<r; i++)
  165.                         if (mark[i]) printf(" r%d", i+1);
  166.                 for (int i=0; i<c; i++)
  167.                         if (mark[i+r]) printf(" c%d", i+1);
  168.                 printf("\n");
  169.         }
  170.         return 0;
  171. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top