图论（二分图最大权独立点集）：COGS 2051. 王者之剑

2051. 王者之剑

★★★☆ 输入文件：Excalibur.in 输出文件：Excalibur.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。

宝石排列在一个n*m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。

开始时刻为0秒。以下操作，每秒按顺序执行

1.在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格（x,y）上，她可以拿走（x，y）中的宝石。

2.在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失

3.若阿尔托利亚·潘德拉贡第i秒开始时在方格（x，y）上，则在第i+1秒可以立即移动到（x+1，y），（x，y+1），（x-1，y）或（x，y-1）上，也可以停留在（x,y)上。

求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

【输入格式】

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

【输出格式】

输出最多可以拿到多少价值宝石

【样例输入】

2 2

1 2

2 1

【样例输出】

【来源】

姚金宇的原创题，有修改

　　可以发现有些细节并不需要去细想。

　　胡博涛论文上有此题的详细解答。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 using namespace std;
  6 const int maxn=10010;
  7 const int maxm=800010;
  8 const int INF=1000000000;
  9 int cnt,tot,fir[maxn],fron[maxn],dis[maxn];
 10 int to[maxm],nxt[maxm],gap[maxn],path[maxn];
 11 int cap[maxm];queue<int>q;
 12 
 13 struct Max_Flow{
 14     void Init(int tot_=0){
 15         tot=tot_;cnt=1;
 16         memset(fir,0,sizeof(fir));
 17         memset(dis,0,sizeof(dis));
 18         memset(gap,0,sizeof(gap));
 19     }
 20     
 21     void add(int a,int b,int c){
 22         nxt[++cnt]=fir[a];
 23         fir[a]=cnt;
 24         cap[cnt]=c;
 25         to[cnt]=b;
 26     }
 27     
 28     void addedge(int a,int b,int c){
 29         add(a,b,c);
 30         add(b,a,0);
 31     }
 32     
 33     bool BFS(int s,int t){
 34         dis[t]=1;q.push(t);
 35         while(!q.empty()){
 36             int x=q.front();q.pop();
 37             for(int i=fir[x];i;i=nxt[i])
 38                 if(!dis[to[i]]){
 39                     dis[to[i]]=dis[x]+1;
 40                     q.push(to[i]);
 41                 }
 42         }
 43         return dis[s];
 44     }
 45     
 46     int Aug(int s,int t,int &p){
 47         int f=INF;
 48         while(p!=s){
 49             f=min(f,cap[path[p]]);
 50             p=to[path[p]^1];
 51         }p=t;
 52         while(p!=s){
 53             cap[path[p]]-=f;
 54             cap[path[p]^1]+=f;
 55             p=to[path[p]^1];
 56         }
 57         return f;
 58     }
 59     
 60     int ISAP(int s,int t){
 61         if(!BFS(s,t))return 0;
 62         for(int i=s;i<=t;i++)fron[i]=fir[i];
 63         for(int i=s;i<=t;i++)gap[dis[i]]+=1;
 64         int p=s,ret=0;
 65         while(dis[s]<=tot){
 66             if(p==t)ret+=Aug(s,t,p);
 67             
 68             for(int &i=fron[p];i;i=nxt[i])
 69                 if(cap[i]&&dis[p]==dis[to[i]]+1){
 70                     path[p=to[i]]=i;
 71                     break;
 72                 }
 73             
 74             if(!fron[p]){
 75                 if(--gap[dis[p]]==0)
 76                     break;
 77                 int Min=tot;
 78                 for(int i=fir[p];i;i=nxt[i])
 79                     if(cap[i])Min=min(Min,dis[to[i]]);
 80                 gap[dis[p]=Min+1]+=1;fron[p]=fir[p];
 81                 if(p!=s)p=to[path[p]^1];    
 82             }    
 83         }
 84         return ret;
 85     }
 86 }isap;
 87 
 88 int n,m;
 89 int main(){
 90     freopen("Excalibur.in","r",stdin);
 91     freopen("Excalibur.out","w",stdout);
 92     scanf("%d%d",&n,&m);
 93     isap.Init(n*m+1);
 94     int s=0,t=n*m+1,ans=0;
 95     for(int i=1;i<=n;i++)
 96         for(int j=1,v;j<=m;j++){
 97             scanf("%d",&v);ans+=v;
 98             int id=(i-1)*m+j;
 99             if((i+j)%2){
100                 isap.addedge(s,id,v);
101                 if(id-m>=1)isap.addedge(id,id-m,INF);
102                 if(id+m<=n*m)isap.addedge(id,id+m,INF);
103                 if(id%m&&id+1<=n*m)isap.addedge(id,id+1,INF);
104                 if((id-1)%m&&id-1>=1)isap.addedge(id,id-1,INF);
105             }
106             else isap.addedge(id,t,v);
107         }
108     printf("%d
",ans-isap.ISAP(s,t));
109     return 0;
110 }