【bzoj1324】【Exca王者之剑】【最小割】
Description
Input
第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵Output
输出最多可以拿到多少块宝石Sample Input
2 21 2
2 1
Sample Output
4 题解：转化一下就是不能选相邻的数。 那我们对图黑白染色。 从源点向黑点连权值的边。 从白点向汇点连权值的边。 黑点和白点之间连正无穷的边。 sum-最小割即可。 代码：#include
#include
#include
#define N 20010
#define M 500010
#define inf 2100000000
using namespace std;
int sum,n,m,point[N],next[M*2],cnt(1),a[110][110];
int dis[N],cur[N],gap[N],pre[N],T,x[4]={0,1,0,-1},y[4]={1,0,-1,0};
struct use{int st,en,v;}e[M*2];
bool f;
void add(int x,int y,int v){next[++cnt]=point[x];point[x]=cnt;e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;next[++cnt]=point[y];point[y]=cnt;e[cnt].st=y;e[cnt].en=x;e[cnt].v=0;
}
int isap(int ss,int tt){int u(ss),i,mn,ans(0);gap[0]=tt;for (i=ss;i<=tt;i++) cur[i]=point[i];while (dis[ss]n||yy<1||yy>m) continue;add(cal(i,j)+1,cal(xx,yy)+1,inf);}}else add(cal(i,j)+1,T,a[i][j]); cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！