一个经典的构图：对格子进行黑白染色，黑白的点分别作XY部的点。
这一题的边就是可以出售的单位面积2的土地，边的端点就是这个土地占用的X部和Y部的两个点。
这样就建好二分图，要求最多土地的答案显然是这个二分图的最大边独立集，也就是最大匹配。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define MAXN 11111 7 #define MAXM 111111 8 #define INF 1<<30 9 struct Edge{ 10 int v,cap,flow,next; 11 }edge[MAXM]; 12 int vs,vt,NE,NV; 13 int head[MAXN]; 14 15 void addEdge(int u,int v,int cap){ 16 edge[NE].v=v; edge[NE].cap=cap; edge[NE].flow=0; 17 edge[NE].next=head[u]; head[u]=NE++; 18 edge[NE].v=u; edge[NE].cap=0; edge[NE].flow=0; 19 edge[NE].next=head[v]; head[v]=NE++; 20 } 21 22 int level[MAXN]; 23 int gap[MAXN]; 24 void bfs(){ 25 memset(level,-1,sizeof(level)); 26 memset(gap,0,sizeof(gap)); 27 level[vt]=0; 28 gap[level[vt]]++; 29 queue que; 30 que.push(vt); 31 while(!que.empty()){ 32 int u=que.front(); que.pop(); 33 for(int i=head[u]; i!=-1; i=edge[i].next){ 34 int v=edge[i].v; 35 if(level[v]!=-1) continue; 36 level[v]=level[u]+1; 37 gap[level[v]]++; 38 que.push(v); 39 } 40 } 41 } 42 43 int pre[MAXN]; 44 int cur[MAXN]; 45 int ISAP(){ 46 bfs(); 47 memset(pre,-1,sizeof(pre)); 48 memcpy(cur,head,sizeof(head)); 49 int u=pre[vs]=vs,flow=0,aug=INF; 50 gap[0]=NV; 51 while(level[vs]