时间戳

首页 > 技术文章 > [COGS 2051] 王者之剑

[COGS 2051] 王者之剑

rvalue 2017-07-31 11:49 原文

Saber大法吼

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

【样例输出】

4

【提示】

在此键入。

【来源】

姚金宇的原创题，有修改

我们注意到如果对这张图进行黑白染色则黑色结点和白色结点有冲突,这时我们可以试着求要舍弃掉的结点,考虑最小割,再用总价值减去这个最小割

($ysf$ $dalao$表示其实是二分图最大权独立集,%%%)

首先进行黑白染色,建立超级源点$s$和$t$,从$s$向所有白色结点连一条容量为该结点价值的边,然后白色结点再向相邻的黑色结点连一条容量为$\infty$的边,最后从黑色结点向$t$连一条容量为该结点价值的边.最后根据最大流最小割定理只需要跑一遍最大流就可以了.

由于中间白色结点连向黑色结点的边权都是$\infty$, 所以最小割一定会选择$s$到白色或者黑色到$t$的边,$\infty$边只是建立一个连接关系.然后这时只需保证图不连通即可保证不冲突,所以求一遍最小割可以得到解.

最后参考代码

GitHub

  1 #include <queue>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 const int MAXV=10010;
  9 const int MAXN=110;
 10 const int INF=0x3FFFFFFF;
 11 
 12 struct Edge{
 13     int from;
 14     int to;
 15     int flow;
 16     Edge* rev;
 17     Edge* next;
 18 };
 19 
 20 Edge* top;
 21 Edge* head[MAXV];
 22 
 23 int m;
 24 int n;
 25 int sum;
 26 int total;
 27 int depth[MAXV];
 28 int data[MAXN][MAXN];
 29 bool color[MAXN][MAXN];
 30 int number[MAXN][MAXN];
 31 
 32 void Initialize();
 33 void Insert(int,int,int);
 34 int Dinic(int,int);
 35 bool BFS(int,int);
 36 int DFS(int,int,int);
 37 int Convert(int,int);
 38 
 39 int main(){
 40     freopen("Excalibur.in","r",stdin);
 41     freopen("Excalibur.out","w",stdout);
 42     Initialize();
 43     printf("%d\n",sum-Dinic(0,m*n+1));
 44     return 0;
 45 }
 46 
 47 int Dinic(int s,int t){
 48     int ans=0;
 49     while(BFS(s,t)){
 50         ans+=DFS(s,INF,t);
 51     }
 52     return ans;
 53 }
 54 
 55 int DFS(int s,int flow,int t){
 56     if(s==t||flow==0)
 57         return flow;
 58     int tmp=flow;
 59     int k;
 60     for(Edge* i=head[s];i!=NULL;i=i->next){
 61         if(i->flow!=0&&tmp!=0&&depth[i->to]==depth[s]+1){
 62             k=DFS(i->to,std::min(tmp,i->flow),t);
 63             if(k==0){
 64                 depth[i->to]=0;
 65                 continue;
 66             }
 67             tmp-=k;
 68             i->flow-=k;
 69             i->rev->flow+=k;
 70             if(tmp==0)
 71                 break;
 72         }
 73     }
 74     return flow-tmp;
 75 }
 76 
 77 bool BFS(int s,int t){
 78     memset(depth,0,sizeof(depth));
 79     std::queue<int> q;
 80     depth[s]=1;
 81     q.push(s);
 82     while(!q.empty()){
 83         s=q.front();
 84         q.pop();
 85         for(Edge* i=head[s];i!=NULL;i=i->next){
 86             if(depth[i->to]==0&&i->flow!=0){
 87                 q.push(i->to);
 88                 depth[i->to]=depth[s]+1;
 89                 if(i->to==t)
 90                     return true;
 91             }
 92         }
 93     }
 94     return false;
 95 }
 96 
 97 inline void Initialize(){
 98     scanf("%d%d",&n,&m);
 99     for(int i=1;i<=n;i++){
100         for(int j=1;j<=m;j++){
101             number[i][j]=++total;
102             scanf("%d",&data[i][j]);
103             sum+=data[i][j];
104             if(i==1)
105                 color[i][j]=!color[i][j-1];
106             else
107                 color[i][j]=!color[i-1][j];
108         }
109     }
110     for(int i=1;i<=n;i++){
111         for(int j=1;j<=m;j++){
112             if(color[i][j]){
113                 Insert(0,Convert(i,j),data[i][j]);
114                 if(i>1)
115                     Insert(Convert(i,j),Convert(i-1,j),INF);
116                 if(i<n)
117                     Insert(Convert(i,j),Convert(i+1,j),INF);
118                 if(j>1)
119                     Insert(Convert(i,j),Convert(i,j-1),INF);
120                 if(j<m)
121                     Insert(Convert(i,j),Convert(i,j+1),INF);
122             }
123             else{
124                 Insert(Convert(i,j),n*m+1,data[i][j]);
125             }
126         }
127     }
128 }
129 
130 inline int Convert(int i,int j){
131     return number[i][j];
132 }
133 
134 inline void Insert(int a,int b,int flow){
135     top=new Edge;
136     Edge* tmp=top;
137     top->from=a;
138     top->to=b;
139     top->flow=flow;
140     top->next=head[a];
141     head[a]=top;
142     top=new Edge;
143     tmp->rev=top;
144     top->from=b;
145     top->to=a;
146     top->flow=0;
147     top->next=head[b];
148     head[b]=top;
149     top->rev=tmp;
150 }
Backup

题面里有个好图所以我就不放了(强行逃

推荐阅读