hdu 4619 Warm up 2 网络流最小割

题意：告诉你一些骨牌，然后骨牌的位置与横竖，这样求最多保留多少无覆盖的方格。
这样的话有人用二分匹配，因为两个必定去掉一个，我用的是最小割，因为保证横着和竖着不连通即可。
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <vector>
  4 #include <iostream>
  5 #include <queue>
  6 #define loop(s,i,n) for(i = s;i < n;i++)
  7 using namespace std;
  8 const int maxn = 2050;
  9 struct edge
 10 {
 11     int u,v,cap,flow;
 12 };
 13 vector<edge>edges;
 14 vector<int>g[maxn],G[maxn];
 15 void addedge(int u,int v,int cap,int flow)
 16 {
 17     //printf("********u %d ****v %d *****
",u,v);
 18     edges.push_back((edge){u,v,cap,flow});
 19     edges.push_back((edge){v,u,0,0});
 20     int m;
 21     m = edges.size();
 22     g[u].push_back(m-2);
 23     g[v].push_back(m-1);
 24 }
 25 void init(int n)
 26 {
 27     int i;
 28     for(i = 0;i <= n;i++)
 29     {
 30         g[i].clear();
 31     }
 32     edges.clear();
 33 }
 34 int vis[maxn],dis[maxn],cur[maxn];
 35 int bfs(int s,int t,int n)
 36 {
 37     memset(vis,0,sizeof(vis));
 38     queue<int>q;
 39     q.push(s);
 40     dis[s] = 0;
 41     vis[s] = 1;
 42     while(!q.empty())
 43     {
 44         int u,v;
 45         u = q.front();
 46         q.pop();
 47         for(int i = 0;i < g[u].size();i++)
 48         {
 49             edge &e = edges[g[u][i]];
 50             v = e.v;
 51             if(!vis[v] && e.cap-e.flow > 0)
 52             {
 53                 vis[v] = 1;
 54                 dis[v] = dis[u] +1;
 55                 q.push(v);
 56             }
 57         }
 58     }
 59     return vis[t];
 60 }
 61 int dfs(int u,int a,int t)
 62 {
 63     if(u == t || a == 0)
 64     return a;
 65     int v;
 66     int flow = 0,f;
 67     for(int& i = cur[u]; i < g[u].size();i++)
 68     {
 69         edge &e = edges[g[u][i]];
 70         v = e.v;
 71         if(dis[u]+1 == dis[v] &&(f = dfs(v,min(a,e.cap-e.flow),t)))
 72         {
 73             e.flow += f;
 74             edges[g[u][i]^1].flow -= f;
 75             flow += f;
 76             a -= f;
 77             if(a == 0)
 78             break;
 79         }
 80     }
 81     return flow;
 82 }
 83 int maxflow(int s,int t)
 84 {
 85     int flow = 0;
 86     while(bfs(s,t,t))
 87     {
 88         memset(cur,0,sizeof(cur));
 89         flow+=dfs(s,1000050,t);
 90     }
 91     return flow;
 92 }
 93 struct node
 94 {
 95     int x1,y1,x2,y2;
 96 }px[2050],py[1050];
 97 int lap(int a,int b)
 98 {
 99     if(py[a].x1 == px[b].x1 && py[a].y1 == px[b].y1)
100     return 1;
101     if(py[a].x2 == px[b].x1 && py[a].y2 == px[b].y1)
102     return 1;
103     if(py[a].x1 == px[b].x2 && py[a].y1 == px[b].y2)
104     return 1;
105     if(py[a].x2 == px[b].x2 && py[a].y2 == px[b].y2)
106     return 1;
107     return 0;
108 }
109 int main()
110 {
111     int n,m;
112     while(scanf("%d%d",&n,&m)&&(m||n))
113     {
114         int i,j;
115         int x,y;
116         init(m+n+5);
117         for(i = 0;i < n;i++)
118         {
119             scanf("%d %d",&x,&y);
120             px[i].x1 = x;
121             px[i].y2 =  px[i].y1 = y;
122             px[i].x2 = x+1;
123         }
124         for(j = 0;j < m;j++)
125         {
126             scanf("%d %d",&x,&y);
127             py[j].x1 = py[j].x2 = x;
128             py[j].y1 = py[j].y2 = y;
129             py[j].y2++;
130         }
131         int cnt;
132         cnt = 0;
133         loop(0,i,n)
134         addedge(0,i+1,1,0);
135         loop(0,j,m)
136         addedge(n+j+1,m+n+1,1,0);
137         loop(0,i,n)
138         {
139             loop(0,j,m)
140             {
141                 if(lap(j,i))
142                 addedge(i+1,j+n+1,1005,0);
143             }
144         }
145         cout<<m+n-maxflow(0,m+n+1)<<endl;
146     }
147 }
View Code
hdu 4619 Warm up 2 网络流 最小割

hdu 4619 Warm up 2 网络流最小割
