fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 305;
  6. const int MAXM = MAXN * MAXN / 2 * 4;
  7. const int SOURCE = MAXN - 2;
  8. const int DESTINATION = MAXN - 1;
  9. const int inf = 0x3f3f3f3f;
  10.  
  11. int head[MAXN],to[MAXM],nxt[MAXM],cap[MAXM],temphead[MAXN];
  12. int dist[MAXN];
  13. int lst;
  14. int n,m;
  15.  
  16. void add_edge(int f,int t,int cap_)
  17. {
  18.     nxt[lst] = head[f];
  19.     head[f] = lst;
  20.     to[lst] = t;
  21.     cap[lst++] = cap_;
  22. }
  23.  
  24. void add_flow_edge(int f,int t,int cap_)
  25. {
  26.     add_edge(f,t,cap_);
  27.     add_edge(t,f,0);
  28. }
  29.  
  30. void add_bi_flow_edge(int a,int b,int cap_)
  31. {
  32.     add_flow_edge(a,b,cap_);
  33.     add_flow_edge(b,a,cap_);
  34. }
  35.  
  36. int bfs()
  37. {
  38.     memset(dist,0x3f,sizeof dist);
  39.     dist[SOURCE] = 0;
  40.     queue<int> q;
  41.     q.push(SOURCE);
  42.     while(q.size())
  43.     {
  44.         int cur = q.front();
  45.         q.pop();
  46.         for(int i=head[cur];i!=-1;i=nxt[i])
  47.         {
  48.             int t = to[i];
  49.             if(cap[i]==0 || dist[t]!=inf)
  50.                 continue;
  51.             dist[t] = dist[cur] + 1,q.push(t);
  52.             if(t == DESTINATION)
  53.                 return true;
  54.         }
  55.     }
  56.     return false;
  57. }
  58.  
  59. int dfs(int cur,int flow)
  60. {
  61.     if(cur == DESTINATION)
  62.         return flow;
  63.     for(int &i=temphead[cur];i!=-1;i=nxt[i])
  64.     {
  65.         int t = to[i];
  66.         int ret;
  67.         if(cap[i] && dist[t] == dist[cur] + 1 && (ret = dfs(t , min(flow,cap[i]))) )
  68.         {
  69.             cap[i] -= ret;
  70.             cap[i^1] += ret;
  71.             return ret;
  72.         }
  73.     }
  74.     return 0;
  75. }
  76.  
  77. int max_flow()
  78. {
  79.     int ret = 0;
  80.     while(bfs())
  81.     {
  82.         memcpy(temphead,head,sizeof head);
  83.         int temp;
  84.         while((temp = dfs(SOURCE,inf)))
  85.             ret += temp;
  86.     }
  87.     return ret;
  88. }
  89.  
  90. int main()
  91. {
  92.     ios::sync_with_stdio(0);
  93.     cin.tie(0);
  94.     while(cin>>n>>m, n||m)
  95.     {
  96.         memset(head,-1,sizeof head);
  97.         lst = 0;
  98.         for(int i=1;i<=n;i++)
  99.         {
  100.             int x;
  101.             cin>>x;
  102.             if(x==0)
  103.                 add_flow_edge(SOURCE,i,1);
  104.             else
  105.                 add_flow_edge(i,DESTINATION,1);
  106.         }
  107.         for(int i=0;i<m;i++)
  108.         {
  109.             int a,b;
  110.             cin>>a>>b;
  111.             add_bi_flow_edge(a,b,1);
  112.         }
  113.         cout<<max_flow()<<"\n";
  114.     }
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0s 4264KB
comments (?)
stdin
copy 
3 3
1 0 0
1 2
1 3
3 2
6 6
1 1 1 0 0 0
1 2
2 3
4 2
3 5
4 5
5 6
0 0
stdout
copy 
1
2
https://ideone.com/Hkl19P
language:
C++14 (gcc 8.3)
created:
8 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!