564 字
3 分钟
[COGS 2051] 王者之剑 题解 网络流最大权闭合子图
【题目描述】
这是在阿尔托利亚·潘德拉贡成为英灵前的事情,她正要去拔出石中剑成为亚瑟王,在这之前她要去收集一些宝石。
宝石排列在一个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 21 22 1
【样例输出】
4
与网络流24题中方格取数相同
最大权闭合子图
黑白染色
相邻连INF的边
源点向白格子连格子权值的边
黑格子想汇点连权值的边
跑一遍最小割也就是最大流 Dinic解决
/* * @Author: WildRage * @Date: 2017-06-13 16:37:09 * @Last Modified by: WildRage * @Last Modified time: 2017-06-13 16:37:09 */#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int INF=0x7fffffff;struct edge{ int END,cap,next;}v[500000];int first[10005],p;void add(int a,int b,int c){ v[p].END=b;v[p].next=first[a];v[p].cap=c;first[a]=p++; v[p].END=a;v[p].next=first[b];v[p].cap=0;first[b]=p++;}int dis[10005];bool vis[10005];bool BFS(int S,int E){ memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); queue<int> Q; Q.push(S); dis[S]=0;vis[S]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=first[u];i!=-1;i=v[i].next){ if(!vis[v[i].END]&&v[i].cap>0){ vis[v[i].END]=1; dis[v[i].END]=dis[u]+1; if(v[i].END==E)return 1; Q.push(v[i].END); } } } return 0;}int DFS(int x,int a,int E){ if(x==E||a==0)return a; int flow=0,f; for(int i=first[x];i!=-1;i=v[i].next){ if(dis[x]+1==dis[v[i].END]&&(f=DFS(v[i].END,min(a,v[i].cap),E))>0){ v[i].cap-=f; v[i^1].cap+=f; flow+=f; a-=f; if(a==0)break; } } if(!flow)dis[x]=-1; return flow;}int Dinic(int S,int E){ int flow=0; while(BFS(S,E)){ flow+=DFS(S,INF,E); } return flow;}int a[105][105];template<class T>inline void read(T &res){ static char ch;T flag=1; while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48; while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;}int Main(){ freopen("Excalibur.in","r",stdin); freopen("Excalibur.out","w",stdout); memset(first,-1,sizeof(first)); int m,n; int sum=0; read(m),read(n); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++){ read(a[i][j]); sum+=a[i][j]; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if((i&1)^(j&1)){ add(0,n*(i-1)+j,a[i][j]); if(j-1>=1)add(n*(i-1)+j,n*(i-1)+j-1,INF); if(i-1>=1)add(n*(i-1)+j,n*(i-2)+j,INF); if(i+1<=m)add(n*(i-1)+j,n*(i)+j,INF); if(j+1<=n)add(n*(i-1)+j,n*(i-1)+j+1,INF); } else{ add(n*(i-1)+j,n*m+1,a[i][j]); }
} } return printf("%d",sum-Dinic(0,m*n+1));}int A=Main();int main(){;}
[COGS 2051] 王者之剑 题解 网络流最大权闭合子图
https://www.nekomio.com/posts/5/