HDu 1565格子取数(1)(最小割)
2748 ワード
グリッド数(1)
Problem Description
n*nの格子の碁盤をあげて、各格子の中に非負の数があります.
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
Output
各テストインスタンスについて、取得可能な最大和を出力します.
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
Author
ailyanlu
Source
Happy 2007
ソースポイントとポイントs,tの設定
ソースポイントと白ポイントがエッジに接続され、容量は白ポイントの数です.
黒い点と合流点は縁を結んで、容量は黒い点の上の数です
白い点は彼の周囲の黒い点とつながっていて、容量はinfです
これにより、ソースポイントと送金ポイントが接続されたくないように、この図の最小分割のみが要求され、残りの数字が求められます.
定理最小割=最大流#include <iostream>
#include <cstdio>
#include <cstring>
#include<queue>
#define maxn 555
#define inf 9999999
using namespace std;
int map[maxn][maxn],tag[maxn],pre[maxn],f[maxn];
int a[maxn][maxn];
int n,s,t,ans,tot,N=99;
int q[maxn],bot,top;
void init()
{
s=0,t=n*n+1,ans=tot=0;
memset(map,0,sizeof(map));
}
void graph()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i+j)%2==1)
{
int cur=i*n+j-n;
map[s][cur]+=a[i][j];
if (i>1) map[cur][cur-n]=inf;
if (i<n) map[cur][cur+n]=inf;
if (j>1) map[cur][cur-1]=inf;
if (j<n) map[cur][cur+1]=inf;
}
else map[i*n+j-n][t]+=a[i][j];
}
void bfs()
{
int u,v;
queue<int>q;
while(1)
{
memset(f,0,sizeof(f));
f[s]=inf;
while(!q.empty())
q.pop();
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
for(v=s;v<=t;v++)
{
if(!f[v]&&map[u][v]>0)
{
pre[v]=u;
q.push(v);
f[v]=min(f[u],map[u][v]);
}
}
if(f[t])
break;
}
if(f[t]==0)
break;
ans+=f[t];
for(int i=t;i!=s;i=pre[i])
{
map[pre[i]][i]-=f[t];
map[i][pre[i]]+=f[t];
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]),tot+=a[i][j];
graph();
bfs();
printf("%d
",tot-ans);
}
return 0;
}
3
75 15 21
75 15 28
34 70 5
188
#include <iostream>
#include <cstdio>
#include <cstring>
#include<queue>
#define maxn 555
#define inf 9999999
using namespace std;
int map[maxn][maxn],tag[maxn],pre[maxn],f[maxn];
int a[maxn][maxn];
int n,s,t,ans,tot,N=99;
int q[maxn],bot,top;
void init()
{
s=0,t=n*n+1,ans=tot=0;
memset(map,0,sizeof(map));
}
void graph()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if((i+j)%2==1)
{
int cur=i*n+j-n;
map[s][cur]+=a[i][j];
if (i>1) map[cur][cur-n]=inf;
if (i<n) map[cur][cur+n]=inf;
if (j>1) map[cur][cur-1]=inf;
if (j<n) map[cur][cur+1]=inf;
}
else map[i*n+j-n][t]+=a[i][j];
}
void bfs()
{
int u,v;
queue<int>q;
while(1)
{
memset(f,0,sizeof(f));
f[s]=inf;
while(!q.empty())
q.pop();
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
for(v=s;v<=t;v++)
{
if(!f[v]&&map[u][v]>0)
{
pre[v]=u;
q.push(v);
f[v]=min(f[u],map[u][v]);
}
}
if(f[t])
break;
}
if(f[t]==0)
break;
ans+=f[t];
for(int i=t;i!=s;i=pre[i])
{
map[pre[i]][i]-=f[t];
map[i][pre[i]]+=f[t];
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]),tot+=a[i][j];
graph();
bfs();
printf("%d
",tot-ans);
}
return 0;
}