题意：给你一个n*m的地，然后给你p个点，表示这些点代表的地是不能卖的，问你最多能卖出多少块1*2的地。
找出i+j为奇数的且能卖的地，作为集合1，与这块地相邻的且能卖的地为集合2，这就转化为最大二分匹配了。
#include #include #include #include #include #include #include #include #include #define LL long long #define maxn 105 #define INF 999999999 using namespace std; struct point { int x,y; }w[5]; int n,m; int f[maxn][maxn]; int flag[maxn*maxn],vis[maxn*maxn]; vector G[maxn*maxn]; //用来储存相连接的且能卖的地 set s; //用来储存那几块地是卖掉的 set ::iterator it; bool cmp(point a,point b) { if(a.x==b.x) return a.y >n>>m) { if(n==0 && m==0) break; memset(f,0,sizeof(f)); s.clear(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { f[i][j]=1; } } memset(flag,0,sizeof(flag)); for(int i=0;i<=n*m;i++) G[i].clear(); int p; cin>>p; while(p--) { int u,v; cin>>u>>v; f[u][v]=0; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(f[i][j]==1) { if((i+j)%2==1) //存入与这块地相连且能卖的地 { if(f[i][j+1]==1) G[(i-1)*m+j].push_back((i-1)*m+j+1); if(f[i][j-1]==1) G[(i-1)*m+j].push_back((i-1)*m+j-1); if(f[i-1][j]==1) G[(i-1)*m+j].push_back((i-2)*m+j); if(f[i+1][j]==1) G[(i-1)*m+j].push_back((i)*m+j); } } } } int ans=match(); printf("%d\n",ans); for(it=s.begin();it!=s.end();it++) { int num=*it; w[0].y=num%m; if(w[0].y==0) w[0].y+=m; w[0].x=((num-w[0].y)/m+1); w[1].y=flag[num]%m; if(w[1].y==0) w[1].y+=m; w[1].x=((flag[num]-w[1].y)/m+1); sort(w,w+2,cmp); printf("(%d,%d)--(%d,%d)\n",w[0].x,w[0].y,w[1].x,w[1].y); } printf("\n"); } return 0; }