BZOJ 1324: Exca王者之剑

1324: Exca王者之剑

Description

BZOJ 1324: Exca王者之剑
BZOJ 1324: Exca王者之剑

Input

第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵

Output

输出最多可以拿到多少块宝石

Sample Input

2 2

1 2
2 1

Sample Output

4

——分割线——

这道题是一个最小割的模型。

代码:

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; inline int remin(int a,int b){
if (a<b) return a;
return b;
}
const int inf=214748360; const int Maxm=100000;
struct EdgeNode{
int u;
int v;
int f;
int nxt;
EdgeNode(){}
EdgeNode(int a,int b,int c,int d){
u=a;
v=b;
f=c;
nxt=d;
}
};
int nume=1;
EdgeNode e[Maxm+5]; const int Maxn=10000;
int src,sink;
int g[Maxn+7]; inline void insertEdgeFunction(int u,int v,int f){
e[++nume]=EdgeNode(u,v,f,g[u]);
g[u]=nume;
}
inline void insert(int u,int v,int f){
insertEdgeFunction(u,v,f);
insertEdgeFunction(v,u,0);
} queue<int> que;
int dist[Maxn+5];
inline bool Bfs(){
while(!que.empty()) que.pop();
memset(dist,-1,sizeof(dist));
que.push(src);
dist[src]=0;
while(!que.empty()){
int point=que.front();
que.pop();
for(int i=g[point];i;i=e[i].nxt){
if (e[i].f!=0 && dist[e[i].v]==-1){
que.push(e[i].v);
dist[e[i].v]=dist[point]+1;
}
}
}
return dist[sink]!=-1;
} int Dfs(int p,int delta){
int ret=0;
if (p==sink){
return delta;
}else{
for (int i=g[p];i;i=e[i].nxt){
if (dist[e[i].v]==dist[p]+1 && e[i].f!=0){
int dret=Dfs(e[i].v,remin(e[i].f,delta));
//printf("%d\n",dret);
ret+=dret;
e[i].f-=dret;
e[i^1].f+=dret;
delta-=dret;
}
}
}
return ret;
} inline int Dinic(){
int ret=0;
while(Bfs()){
ret+=Dfs(src,inf);
}
return ret;
} int n,m;
int sum=0;
int map[105][105];
int hash[105][105];
int cnt=0;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
scanf("%d",&map[i][j]);
sum+=map[i][j];
hash[i][j]=++cnt;
}
}
src=0;
sink=cnt+1;
for(int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if ((i+j+1)&1){
insert(src,hash[i][j],map[i][j]);
}else{
insert(hash[i][j],sink,map[i][j]);
}
if ((i+j+1)&1){
int dx[]={0,1,0,-1,0};
int dy[]={0,0,1,0,-1};
for (int k=1;k<=4;k++){
int x=i+dx[k],y=j+dy[k];
if (1<=x && x<=n && 1<=y && y<=m) insert(hash[i][j],hash[x][y],inf);
}
}
}
} printf("%d\n",sum-Dinic()); return 0;
}
上一篇:一起学爬虫——PyQuery常用用法总结


下一篇:SQL Server日期和时间的格式