记录编号 | 430976 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | 王者之剑 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.043 s | ||
提交时间 | 2017-07-30 21:24:08 | 内存使用 | 11.85 MiB | ||
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; inline int read(){ int sum(0); char ch(getchar()); for(;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); return sum; } struct edge{ int e,n,w; }a[2000001]; int pre[100001],tot; inline void insert(int s,int e,int w){ a[tot].e=e; a[tot].w=w; a[tot].n=pre[s]; pre[s]=tot++; } int n,m; int w[105][105],col[105][105]; inline void paint(){ int now(1); for(int i=1;i<=n;i++){ now^=1; for(int j=1;j<=m;j++){ if(j&1) col[i][j]=now; else col[i][j]=now^1; } } } int S(0),T; int ans(0),inf(0x7fffffff),sum(0); inline void build(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(col[i][j]) insert(S,(i-1)*m+j,w[i][j]),insert((i-1)*m+j,S,0); else insert((i-1)*m+j,T,w[i][j]),insert(T,(i-1)*m+j,0); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(col[i][j]){ if(i!=1) insert((i-2)*m+j,(i-1)*m+j,0),insert((i-1)*m+j,(i-2)*m+j,inf); if(i!=n) insert(i*m+j,(i-1)*m+j,0),insert((i-1)*m+j,i*m+j,inf); if(j!=1) insert((i-1)*m+j-1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j-1,inf); if(j!=m) insert((i-1)*m+j+1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j+1,inf); } } } int dis[10010]; inline bool bfs(int s,int t){ memset(dis,0,sizeof(dis)); dis[s]=1; queue<int>q; q.push(s); while(!q.empty()){ int k(q.front()); q.pop(); for(int i=pre[k];i!=-1;i=a[i].n){ int e(a[i].e); if(!dis[e]&&a[i].w){ dis[e]=dis[k]+1; q.push(e); if(e==t) return true; } } } return false; } inline int my_min(int a,int b){ return a<b?a:b; } inline int dfs(int now,int flow){ if(now==T) return flow; int tmp(flow),f; for(int i=pre[now];i!=-1;i=a[i].n){ int e(a[i].e); if(dis[e]==dis[now]+1&&tmp&&a[i].w){ f=dfs(e,my_min(tmp,a[i].w)); if(!f){ dis[e]=0; continue; } a[i].w-=f; a[i^1].w+=f; tmp-=f; } } return flow-tmp; } inline int gg(){ freopen("Excalibur.in","r",stdin); freopen("Excalibur.out","w",stdout); memset(pre,-1,sizeof(pre)); n=read(),m=read(); T=n*m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) w[i][j]=read(),sum+=w[i][j]; paint(); build(); while(bfs(S,T)) ans+=dfs(S,inf); printf("%d",sum-ans); return 0; } int K(gg()); int main(){;}