首页 > 代码库 > Bzoj1324 Exca王者之剑
Bzoj1324 Exca王者之剑
Submit: 591 Solved: 296
Description
Input
第一行给出数字N,M代表行列数.N,M均小于等于100 下面N行M列用于描述数字矩阵
Output
输出最多可以拿到多少块宝石
Sample Input
2 2
1 2
2 1
1 2
2 1
Sample Output
4
HINT
Source
2007Amber国家队论文
图论 网络流
将图二分染色
求最大点权独立集
最大点权独立集就等于总权值和减去最小权值覆盖
最小权值覆盖就是建好二分图以后的最小割
也就是说这是道模板题
然而我居然没有1A,原因是反向弧的流量建成了w而不是0
真鸡儿丢人,我退群吧
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std; 10 const int INF=0x3f3f3f3f; 11 const int mxn=100010; 12 const int mx[5]={0,1,0,-1,0}; 13 const int my[5]={0,0,1,0,-1}; 14 int read(){ 15 int x=0,f=1;char ch=getchar(); 16 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 17 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 18 return x*f; 19 } 20 struct edge{ 21 int v,nxt,f; 22 }e[mxn<<1]; 23 int hd[mxn],mct=1; 24 void add_edge(int u,int v,int w){ 25 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=w; hd[u]=mct;return; 26 } 27 void insert(int u,int v,int w){ 28 add_edge(u,v,w);add_edge(v,u,0);return; 29 } 30 queue<int>q; 31 int d[mxn]; 32 int n,m,S,T; 33 bool BFS(){ 34 memset(d,0,sizeof d); 35 d[S]=1; 36 q.push(S); 37 while(!q.empty()){ 38 int u=q.front();q.pop(); 39 for(int i=hd[u];i;i=e[i].nxt){ 40 int v=e[i].v; 41 if(e[i].f && !d[v]){ 42 d[v]=d[u]+1; 43 q.push(v); 44 } 45 } 46 } 47 return d[T]; 48 } 49 int DFS(int u,int lim){ 50 if(u==T)return lim; 51 int f=0,tmp; 52 for(int i=hd[u],v;i;i=e[i].nxt){ 53 v=e[i].v; 54 if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){ 55 e[i].f-=tmp; e[i^1].f+=tmp; 56 lim-=tmp; f+=tmp; 57 if(!lim)return f; 58 } 59 } 60 d[u]=0; 61 return f; 62 } 63 int Dinic(){ 64 int res=0; 65 while(BFS())res+=DFS(S,0x3f3f3f3f); 66 return res; 67 } 68 int id[120][120]; 69 int mp[120][120]; 70 int smm=0,dt=0; 71 void solve(){ 72 int i,j; 73 for(i=1;i<=n;i++) 74 for(j=1;j<=m;j++) 75 id[i][j]=++dt; 76 S=0;T=dt+1; 77 for(i=1;i<=n;i++) 78 for(j=1;j<=m;j++){ 79 if((i+j)&1){ 80 insert(S,id[i][j],mp[i][j]); 81 for(int k=1;k<=4;k++){ 82 int nx=i+mx[k],ny=j+my[k]; 83 if(nx>0 && nx<=n && ny>0 && ny<=m) 84 insert(id[i][j],id[nx][ny],INF); 85 86 } 87 } 88 else insert(id[i][j],T,mp[i][j]); 89 } 90 return; 91 } 92 int main(){ 93 int i,j; 94 n=read();m=read(); 95 for(i=1;i<=n;i++) 96 for(j=1;j<=m;j++){ 97 mp[i][j]=read(); 98 smm+=mp[i][j]; 99 }100 solve();101 int res=Dinic();102 // printf("Res:%d\n",res);103 printf("%d\n",smm-res);104 return 0;105 }
Bzoj1324 Exca王者之剑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。