SCU3185 Black and white（二分图最大点权独立集）

题目大概说有几个黑色、白色矩阵，问能选出黑白不相交的矩形面积和的最大值。

建二分图，黑色矩阵为X部的点，白色为Y部，XY的点权都为其矩阵面积，如果有个黑白矩阵相交则它们之间有一条边，那样问题就是要从这个二分图中选出最大的点使其没有公共边且点权和最大。

即二分图的最大点权独立集。可以建容量网络用最小割求解，在二分图基础上加源点汇点，源点向X部连容量为权值的边，Y部向汇点连容量为权值的边，X部与Y部的无向边改为容量INF的有向边，最后的结果就是所有点权和-最小割。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 using namespace std;
  6 #define INF (1<<30)
  7 #define MAXN 444
  8 #define MAXM 444*444*2
  9 struct Edge{
 10     int v,cap,flow,next;
 11 }edge[MAXM];
 12 int vs,vt,NV,NE,head[MAXN];
 13 void addEdge(int u,int v,int cap){
 14     edge[NE].v=v; edge[NE].cap=cap; edge[NE].flow=0;
 15     edge[NE].next=head[u]; head[u]=NE++;
 16     edge[NE].v=u; edge[NE].cap=0; edge[NE].flow=0;
 17     edge[NE].next=head[v]; head[v]=NE++;
 18 }
 19 int level[MAXN];
 20 int gap[MAXN];
 21 void bfs(){
 22     memset(level,-1,sizeof(level));
 23     memset(gap,0,sizeof(gap));
 24     level[vt]=0;
 25     gap[level[vt]]++;
 26     queue<int> que;
 27     que.push(vt);
 28     while(!que.empty()){
 29         int u=que.front(); que.pop();
 30         for(int i=head[u]; i!=-1; i=edge[i].next){
 31             int v=edge[i].v;
 32             if(level[v]!=-1) continue;
 33             level[v]=level[u]+1;
 34             gap[level[v]]++;
 35             que.push(v);
 36         }
 37     }
 38 }
 39 int pre[MAXN];
 40 int cur[MAXN];
 41 int ISAP(){
 42     bfs();
 43     memset(pre,-1,sizeof(pre));
 44     memcpy(cur,head,sizeof(head));
 45     int u=pre[vs]=vs,flow=0,aug=INF;
 46     gap[0]=NV;
 47     while(level[vs]<NV){
 48         bool flag=false;
 49         for(int &i=cur[u]; i!=-1; i=edge[i].next){
 50             int v=edge[i].v;
 51             if(edge[i].cap!=edge[i].flow && level[u]==level[v]+1){
 52                 flag=true;
 53                 pre[v]=u;
 54                 u=v;
 55                 aug=min(aug,edge[i].cap-edge[i].flow);
 56                 if(v==vt){
 57                     flow+=aug;
 58                     for(u=pre[v]; v!=vs; v=u,u=pre[u]){
 59                         edge[cur[u]].flow+=aug;
 60                         edge[cur[u]^1].flow-=aug;
 61                     }
 62                     aug=INF;
 63                 }
 64                 break;
 65             }
 66         }
 67         if(flag) continue;
 68         int minlevel=NV;
 69         for(int i=head[u]; i!=-1; i=edge[i].next){
 70             int v=edge[i].v;
 71             if(edge[i].cap!=edge[i].flow && level[v]<minlevel){
 72                 minlevel=level[v];
 73                 cur[u]=i;
 74             }
 75         }
 76         if(--gap[level[u]]==0) break;
 77         level[u]=minlevel+1;
 78         gap[level[u]]++;
 79         u=pre[u];
 80     }
 81     return flow;
 82 }
 83 struct Rect{
 84     int x1,y1,x2,y2;
 85 }black[222],white[222];
 86 bool isOver(Rect &r1,Rect &r2){
 87     if(r1.x1>=r2.x2 || r2.x1>=r1.x2 || r1.y1>=r2.y2 || r2.y1>=r1.y2) return 0;
 88     return 1;
 89 }
 90 int getArea(Rect &r){
 91     return (r.x2-r.x1)*(r.y2-r.y1);
 92 }
 93 int main(){
 94     int t,n,m,x1,y1,x2,y2;
 95     scanf("%d",&t);
 96     while(t--){
 97         scanf("%d%d",&n,&m);
 98         vs=0; vt=n+m+1; NV=vt+1; NE=0;
 99         memset(head,-1,sizeof(head));
100         int tot=0;
101         for(int i=1; i<=n; ++i){
102             scanf("%d%d%d%d",&black[i].x1,&black[i].y1,&black[i].x2,&black[i].y2);
103             addEdge(vs,i,getArea(black[i]));
104             tot+=getArea(black[i]);
105         }
106         for(int i=1; i<=m; ++i){
107             scanf("%d%d%d%d",&white[i].x1,&white[i].y1,&white[i].x2,&white[i].y2);
108             addEdge(i+n,vt,getArea(white[i]));
109             tot+=getArea(white[i]);
110         }
111         for(int i=1; i<=n; ++i){
112             for(int j=1; j<=m; ++j){
113                 if(isOver(black[i],white[j])) addEdge(i,j+n,INF);
114             }
115         }
116         printf("%d
",tot-ISAP());
117     }
118     return 0;
119 }