srm 558 div1 1000 SurroundingGame(最小割構圖題)

1. Problem Statement
2. Definition
3. Constraints
4. Examples

Problem Statement

Surrounding Game is a single-player game played on a rectangular grid of cells. Cells are considered adjacent if they share a common side. (Hence, each cell has at most four adjacent cells. The cells on the sides and in the corners of the grid have fewer
adjacent cells than the ones inside the grid.)

The game is played by placing stones into some of the cells. Each cell may only contain at most one stone. A cell is called dominated if at least one of the following two conditions holds:

The cell contains a stone.
All cells adjacent to the cell contain stones.

Each cell of the grid contains two numbers, each from 0 to 61, inclusive: the cost of placing a stone into the cell, and the benefit from dominating the cell. At the end of the game, the overall score of the player is the sum of all benefits minus the sum of
all costs.

You are given the vector <string>s cost and benefit. The characters cost[i][j] and benefit[i][j] represent the two numbers written in the cell (i,j), using the following encoding:

Characters ‘0’-‘9’ represent numbers 0-9.
Characters ‘a’-‘z’ represent numbers 10-35.
Characters ‘A’-‘Z’ represent numbers 36-61.

For example, if character 7 of element 4 of cost is ‘B’, the cost of placing a stone into the cell (4,7) is 37.

Calculate and return the maximal possible score for the given grid.

Definition

Class:	SurroundingGame
Method:	maxScore
Parameters:	vector <string>, vector <string>
Returns:	int
Method signature:	int maxScore(vector <string> cost, vector <string> benefit)
(be sure your method is public)

Constraints

–

cost will contain between 2 and 20 elements, inclusive.

–

cost and benefit will contain the same number of elements.

–

Each element of cost will contain between 2 and 20 characters, inclusive.

–

Each element of cost will contain the same number of characters.

–

Each element of benefit will contain the same number of characters as element 0 of cost.

–

Each character in cost and benefit will be a character from ‘0’-‘9′,’a’-‘z’, or ‘A’-‘Z’.

Examples

{"21","12"}

{"21","12"}

Returns: 4

The optimal solution is to put stones into (0,1) and (1,0). All the cells will be dominated and the overall score will be 6 – 2 = 4.

{"ZZ","ZZ"}

{"11","11"}

Returns: 0

The optimal solution is to put no stones. It is impossible to get a positive score.

{"XXX","XXX","XXX"}

{"aaa","aZa","aaa"}

Returns: 2

The optimal solution is to put a stone into (1,1).

{"asam","atik"}

{"123A","45BC"}

Returns: 71

{"IIIIIIII",
"IIWWWWII",
"IIWIIIII",
"IIWIIIII",
"IIWWWWII",
"IIIIIWII",
"IIIIIWII",
"IIWWWWII",
"IIIIIIII"}

{"IIIIIIII",
"II0000II",
"II0II0II",
"II0II0II",
"II0000II",
"II0II0II",
"II0II0II",
"II0000II",
"IIIIIIII"}

Returns: 606

題意：給你一個n*m的方陣，每個方陣可以放石頭，每個格子放石頭需要花費，對於一個格子，如果放了石頭，或者它周圍的格子都放了石頭，則它將帶來收益。。。問，怎樣放石頭，使得收益-花費的值最大

分析：類似這樣的題做得挺多，看完不久，便想到可能是最小割的應用，然後就是長久的掙扎，下面就說說別人的構圖吧，我自己還沒完全明白= = 看了很多人的程式碼，就下面這個構圖簡單，而且明白一點點

首先將所有格子黑白塗色，將每個格子分成兩個節點，然後虛擬源點S和匯點T，對於黑色格子i，建兩條邊，S到i，容量為花費，i到i’容量為收益，對於白色格子j，也是兩條邊，j到T，容量為花費，j’到j容量為收益，對於i與j相鄰的，也建立兩條邊，i到j’，和i’到j，容量都是無窮，這樣做最大流，答案就是所有收益-最大流的值

仔細推敲了下，這個模型是假設取了所有格子的收益，然後怎樣擺放石子，使得花費最小，也就是這個模型就是求最小花費的，中間兩條容量為收益的邊正好限制花費不超過收益，在這個前提下，使得總花費最小，這就是我大概的理解

希望有誰會這道題，指導我下

PS：由於比賽時做完一題就剩20分鐘，弱菜無力。。。看完這題就剩6分鐘了，立馬貼了個模板，隨便構圖，最後樣例都調不出來，本來後悔不應該中途放鬆的，比賽後才發現就算做了我也做不出來，這題不是簡單題 T_T

冥思苦想了兩天，還是沒想出怎樣構圖，無奈看了別人的程式碼，還是懵懵懂懂，不過這回ID變黃了，貼下來當紀念吧，嘿嘿

程式碼：

// BEGIN CUT HERE
// END CUT HERE
#line 5 "SurroundingGame.cpp"
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<sstream>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<fstream>
#include<numeric>
#include<iomanip>
#include<bitset>
#include<list>
#include<stdexcept>
#include<functional>
#include<utility>
#include<ctime>
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(i=0;i<(n);  i)
#define FOR(i,l,h) for(i=(l);i<=(h);  i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
const int mm=1000000;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;  i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c)
{
reach[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge  ;
reach[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge  ;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;  i)dis[i]=-1;
dis[q[r  ]=src]=0;
for(l=0;l<r;  l)
for(i=head[u=q[l]];i>=0;i=next[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r  ]=v]=dis[u] 1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=next[i])
if(flow[i]&&dis[v=reach[i]]==dis[u] 1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1] =tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;  i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret =delta;
}
return ret;
}
int get(char a)
{
if(a>='0'&&a<='9')return a-'0';
if(a>='a'&&a<='z')return a-'a' 10;
if(a>='A'&&a<='Z')return a-'A' 36;
return 0;
}
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
class SurroundingGame
{
public:
int maxScore(vector <string> cost, vector <string> benefit)
{
int i,j,k,x,y,n=cost.size(),m=cost[0].size(),sum=0;
prepare(n*m*2 2,0,n*m*2 1);
for(i=0;i<n;  i)
for(j=0;j<m;  j)
{
sum =get(benefit[i][j]);
if((i j)%2)
{
addedge(src,i*m j 1,get(cost[i][j]));
addedge(i*m j 1,n*m i*m j 1,get(benefit[i][j]));
}
else
{
addedge(n*m i*m j 1,i*m j 1,get(benefit[i][j]));
addedge(i*m j 1,dest,get(cost[i][j]));
}
for(k=0;k<4;  k)
{
x=i dx[k];
y=j dy[k];
if(x<0||x>=n||y<0||y>=m)continue;
if((i j)%2)addedge(n*m i*m j 1,x*m y 1,oo);
else addedge(x*m y 1,n*m i*m j 1,oo);
}
}
sum-=Dinic_flow();
return sum;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end();   iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
void test_case_0() { string Arr0[] = {"21","12"}; vector <string> Arg0(Arr0, Arr0   (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"21","12"}; vector <string> Arg1(Arr1, Arr1   (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; verify_case(0, Arg2, maxScore(Arg0, Arg1)); }
void test_case_1() { string Arr0[] = {"ZZ","ZZ"}; vector <string> Arg0(Arr0, Arr0   (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"11","11"}; vector <string> Arg1(Arr1, Arr1   (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(1, Arg2, maxScore(Arg0, Arg1)); }
void test_case_2() { string Arr0[] = {"XXX","XXX","XXX"}; vector <string> Arg0(Arr0, Arr0   (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"aaa","aZa","aaa"}; vector <string> Arg1(Arr1, Arr1   (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, maxScore(Arg0, Arg1)); }
void test_case_3() { string Arr0[] = {"asam","atik"}; vector <string> Arg0(Arr0, Arr0   (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"123A","45BC"}; vector <string> Arg1(Arr1, Arr1   (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 71; verify_case(3, Arg2, maxScore(Arg0, Arg1)); }
void test_case_4() { string Arr0[] = {"IIIIIIII",
"IIWWWWII",
"IIWIIIII",
"IIWIIIII",
"IIWWWWII",
"IIIIIWII",
"IIIIIWII",
"IIWWWWII",
"IIIIIIII"}
; vector <string> Arg0(Arr0, Arr0   (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"IIIIIIII",
"II0000II",
"II0II0II",
"II0II0II",
"II0000II",
"II0II0II",
"II0II0II",
"II0000II",
"IIIIIIII"}
; vector <string> Arg1(Arr1, Arr1   (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 606; verify_case(4, Arg2, maxScore(Arg0, Arg1)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
SurroundingGame ___test;
___test.run_test(-1);
return 0;
}
// END CUT HERE