首页 > 代码库 > Bzoj1324 Exca王者之剑

Bzoj1324 Exca王者之剑

2024-09-10 22:46:22   220人阅读

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 591  Solved: 296

Description

技术分享 技术分享

Input

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

Output

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

Sample Input

2 2
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王者之剑


联系
我们