Warm up 2
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 656 Accepted Submission(s): 329
Problem Description
Some 1×2 dominoes are placed on a plane. Each dominoe is placed either horizontally or vertically. It's guaranteed the dominoes in the same direction are not overlapped, but horizontal and vertical dominoes may overlap with each other. You task is to remove some dominoes, so that the remaining dominoes do not overlap with each other. Now, tell me the maximum number of dominoes left on the board.
Input
There are multiple input cases.
The first line of each case are 2 integers: n(1 <= n <= 1000), m(1 <= m <= 1000), indicating the number of horizontal and vertical dominoes.
Then n lines follow, each line contains 2 integers x (0 <= x <= 100) and y (0 <= y <= 100), indicating the position of a horizontal dominoe. The dominoe occupies the grids of (x, y) and (x + 1, y).
Then m lines follow, each line contains 2 integers x (0 <= x <= 100) and y (0 <= y <= 100), indicating the position of a horizontal dominoe. The dominoe occupies the grids of (x, y) and (x, y + 1).
Input ends with n = 0 and m = 0.
Output
For each test case, output the maximum number of remaining dominoes in a line.
Sample Input
2 3
0 0
0 3
0 1
1 1
1 3
4 5
0 1
0 2
3 1
2 2
0 0
1 0
2 0
4 1
3 2
0 0
Sample Output
4
6
Source
2013 Multi-University Training Contest 2
Recommend
zhuyuanchen520
題解：
原來是我建圖不會建。。。果然是基礎功不扎實啊。。
原來就是個普通的最大獨立集。 最大獨立集的定義就是所選取的點集合中，任意兩條邊都不相連。 又因為題目中說橫著的不會跟橫著的相連，豎著的不會跟豎著的相連，所以。這是個相當標准的二分圖。就是求X集合跟Y集合的最大獨立集。
建造圖時，X取的是那0到n-1個骨牌 Y取的是後面的0到m-1個骨牌。。。無語撒。。原來當初我2分圖完全弄錯了。。
這題解法好像很多。。什麼搜索，貪心。。不說了。。。牢記不會建圖的教訓。。
我提供下我寫的3份模板代碼吧。。。。
第一份 33MS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
const int maxn=1111;
int g[maxn][maxn];
int cx[maxn],cy[maxn],vst[maxn];
int nx,ny;
int findpath(int u){
for(int v=0;v<ny;v++){
if(!vst[v]&&g[u][v]){
vst[v]=1;
if(cy[v]==-1||findpath(cy[v])){
cy[v]=u,cx[u]=v;
return 1;
}
}
}
return 0;
}
int MaxMatch(){
int ret=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
for(int i=0;i<nx;i++)
if(cx[i]==-1){
memset(vst,0,sizeof(vst));
if(findpath(i))
ret++;
}
return ret;
}
struct node{
int x,y;
}mx[maxn],my[maxn];
int main(){
//freopen("1009.in","r",stdin);
int n,m;
while(scanf("%d %d",&n,&m)&&n+m){
for(int i=0,a,b;i<n;i++){
scanf("%d %d",&a,&b);
mx[i].x=a,mx[i].y=b;
}
for(int i=0,a,b;i<m;i++){
scanf("%d %d",&a,&b);
my[i].x=a,my[i].y=b;
}
memset(g,0,sizeof(g));
for(int i=0,x1,y1;i<n;i++){
x1=mx[i].x,y1=mx[i].y;
for(int j=0,x2,y2;j<m;j++){
x2=my[j].x,y2=my[j].y;
if(x1==x2&&y1==y2
||x1==x2&&y1==y2+1
||x1+1==x2&&y1==y2
||x1+1==x2&&y1==y2+1)
g[i][j]=1;
}
}
nx=n,ny=m;
printf("%d\n",n+m-MaxMatch());
}
return 0;
}
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define clr(x,k) memset((x),(k),sizeof(x))
#define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it)
using namespace std;
typedef vector<int> vi;
const int maxn=1000;
vector<int> gx[maxn];
int cx[maxn],cy[maxn],vst[maxn];
int nx,ny;
int findpath_Vector(int u){
foreach(it,gx[u]){
if(!vst[*it]){
vst[*it]=1;
if(cy[*it]==-1||findpath_Vector(cy[*it])){
cx[u]=*it;
cy[*it]=u;
return 1;
}
}
}
return 0;
}
int maxMatch_Vector(){
int ret=0;
clr(cx,-1),clr(cy,-1);
for(int i=0;i<nx;i++)
if(cx[i]==-1){
clr(vst,0);
if(findpath_Vector(i))
ret++;
}
return ret;
}
struct node{
int x,y;
}mx[maxn],my[maxn];
int main(){
// freopen("1009.in","r",stdin);
int n,m;
while(scanf("%d %d",&n,&m)&&n+m){
for(int i=0,a,b;i<n;i++){
scanf("%d %d",&a,&b);
mx[i].x=a,mx[i].y=b;
}
for(int i=0,a,b;i<m;i++){
scanf("%d %d",&a,&b);
my[i].x=a,my[i].y=b;
}
for(int i=0;i<n;i++)
gx[i].clear();
for(int i=0,x1,y1;i<n;i++){
x1=mx[i].x,y1=mx[i].y;
for(int j=0,x2,y2;j<m;j++){
x2=my[j].x,y2=my[j].y;
if(x1==x2&&y1==y2
||x1==x2&&y1==y2+1
||x1+1==x2&&y1==y2
||x1+1==x2&&y1==y2+1)
gx[i].push_back(j);
}
}
nx=n,ny=m;
printf("%d\n",n+m-maxMatch_Vector());
}
return 0;
}
