题意：告诉你一些骨牌，然后骨牌的位置与横竖，这样求最多保留多少无覆盖的方格。
这样的话有人用二分匹配，因为两个必定去掉一个，我用的是最小割，因为保证横着和竖着不连通即可。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <queue>
#define loop(s,i,n) for(i = s;i < n;i++)
using namespace std;
const int maxn = ;
struct edge
{
int u,v,cap,flow;
};
vector<edge>edges;
vector<int>g[maxn],G[maxn];
void addedge(int u,int v,int cap,int flow)
{
//printf("********u %d ****v %d *****\n",u,v);
edges.push_back((edge){u,v,cap,flow});
edges.push_back((edge){v,u,,});
int m;
m = edges.size();
g[u].push_back(m-);
g[v].push_back(m-);
}
void init(int n)
{
int i;
for(i = ;i <= n;i++)
{
g[i].clear();
}
edges.clear();
}
int vis[maxn],dis[maxn],cur[maxn];
int bfs(int s,int t,int n)
{
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
dis[s] = ;
vis[s] = ;
while(!q.empty())
{
int u,v;
u = q.front();
q.pop();
for(int i = ;i < g[u].size();i++)
{
edge &e = edges[g[u][i]];
v = e.v;
if(!vis[v] && e.cap-e.flow > )
{
vis[v] = ;
dis[v] = dis[u] +;
q.push(v);
}
}
}
return vis[t];
}
int dfs(int u,int a,int t)
{
if(u == t || a == )
return a;
int v;
int flow = ,f;
for(int& i = cur[u]; i < g[u].size();i++)
{
edge &e = edges[g[u][i]];
v = e.v;
if(dis[u]+ == dis[v] &&(f = dfs(v,min(a,e.cap-e.flow),t)))
{
e.flow += f;
edges[g[u][i]^].flow -= f;
flow += f;
a -= f;
if(a == )
break;
}
}
return flow;
}
int maxflow(int s,int t)
{
int flow = ;
while(bfs(s,t,t))
{
memset(cur,,sizeof(cur));
flow+=dfs(s,,t);
}
return flow;
}
struct node
{
int x1,y1,x2,y2;
}px[],py[];
int lap(int a,int b)
{
if(py[a].x1 == px[b].x1 && py[a].y1 == px[b].y1)
return ;
if(py[a].x2 == px[b].x1 && py[a].y2 == px[b].y1)
return ;
if(py[a].x1 == px[b].x2 && py[a].y1 == px[b].y2)
return ;
if(py[a].x2 == px[b].x2 && py[a].y2 == px[b].y2)
return ;
return ;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&(m||n))
{
int i,j;
int x,y;
init(m+n+);
for(i = ;i < n;i++)
{
scanf("%d %d",&x,&y);
px[i].x1 = x;
px[i].y2 = px[i].y1 = y;
px[i].x2 = x+;
}
for(j = ;j < m;j++)
{
scanf("%d %d",&x,&y);
py[j].x1 = py[j].x2 = x;
py[j].y1 = py[j].y2 = y;
py[j].y2++;
}
int cnt;
cnt = ;
loop(,i,n)
addedge(,i+,,);
loop(,j,m)
addedge(n+j+,m+n+,,);
loop(,i,n)
{
loop(,j,m)
{
if(lap(j,i))
addedge(i+,j+n+,,);
}
}
cout<<m+n-maxflow(,m+n+)<<endl;
}
}