建外贸企业网站,关于百度网站是多少,广西桂林天气预报15天查询,中国计算机软考网Description
文理分科是一件很纠结的事情#xff01;#xff08;虽然看到这个题目的人肯定都没有纠结过#xff09; 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述#xff0c;每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学…Description
文理分科是一件很纠结的事情虽然看到这个题目的人肯定都没有纠结过 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到 1如果第i行第秒J的同学选择了文科则他将获得art[i][j]的满意值如果选择理科将得到science[i][j]的满意值。 2如果第i行第J列的同学选择了文科并且他相邻两个格子相邻当且仅当它们拥有一条相同的边的同学全部选择了文科则他会更开心所以会增加same_art[i][j]的满意值。 3如果第i行第j列的同学选择了理科并且他相邻的同学全部选择了理科则增加same_science[i]j[]的满意值。小P想知道大家应该如何选择才能使所有人的满意值之和最大。 请告诉他这个最大值。
Input 第一行为两个正整数nm 接下来n术m个整数表示art[i][j] 接下来n术m个整数表示science[i][j] 接下来n术m个整数表示same_art[i][j]
Output 输出为一个整数表示最大的满意值之和
Sample Input 3 4 13 2 4 13 7 13 8 12 18 17 0 5 8 13 15 4 11 3 8 11 11 18 6 5 1 2 3 4 4 2 3 2 3 1 0 4 3 2 3 2 0 2 2 1 0 2 4 4 Sample Output 152
Hint 样例说明 1表示选择文科0表示选择理科方案如下 1 0 0 1 0 1 0 0 1 0 0 0 N,M100,读入数据均500
solution
非常经典的最小割问题
要么选理科要么选文科
设计两个超级点SSS表示选文科TTT表示选理科
与SSS分在一起的则选的是文科得到artartart否则是理科得到sciencesciencescience
考虑怎么判断可额外增加的满意值
不妨再新添点与SSS连流量same_art的边
怎么保证选了新添点绑在一起的人都一起选文科呢
直接与绑在一起的上下左右中点都连流量infinfinf则一定不会出现在最小割里面
新添点与TTT连流量same_science的边
怎么保证选了新添点绑在一起的人都一起选理科呢
同样的直接与绑在一起的上下左右中点都连流量infinfinf
则一定不会出现在最小割里面
最后就在这个图内跑最大流所有的满意值减去最小割就是真正的最大满意值
code
#include queue
#include cstdio
#include cstring
using namespace std;
#define maxn 200005
#define inf 0x7f7f7f7f
struct node {int nxt, to, flow;
}edge[maxn 1];
queue int q;
int n, m, cnt 1, num;
int dep[maxn], head[maxn], cur[maxn];
int dx[4] { 1, -1, 0, 0 }, dy[4] { 0, 0, 1, -1 };int id( int x, int y ) {return ( x - 1 ) * m y;
}bool inside( int x, int y ) {if( x 1 || x n || y 1 || y m ) return 0;else return 1;
}void addEdge( int u, int v, int w ) {cnt ;edge[cnt].nxt head[u];edge[cnt].to v;edge[cnt].flow w;head[u] cnt;cnt ;edge[cnt].nxt head[v];edge[cnt].to u;edge[cnt].flow 0;head[v] cnt;
}int bfs( int s, int t ) {memcpy( cur, head, sizeof( head ) );memset( dep, 0, sizeof( dep ) );dep[s] 1;q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];i;i edge[i].nxt ) {int v edge[i].to;if( ! dep[v] edge[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int t, int cap ) {if( ! cap || u t ) return cap;int flow 0;for( int i cur[u];i;i edge[i].nxt ) {cur[u] i;int v edge[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, t, min( cap, edge[i].flow ) );if( ! w ) continue;flow w;cap - w;edge[i].flow - w;edge[i ^ 1].flow w;if( ! cap ) break;}}return flow;
}int dinic( int s, int t ) {int ans 0;while( bfs( s, t ) )ans dfs( s, t, inf );return ans;
}int main() {scanf( %d %d, n, m );int ans 0, S 0, T n * m 1, w; num n * m 1;for( int i 1;i n;i )for( int j 1;j m;j ) {scanf( %d, w );addEdge( S, id( i, j ), w );ans w;}for( int i 1;i n;i )for( int j 1;j m;j ) {scanf( %d, w );addEdge( id( i, j ), T, w );ans w;}for( int i 1;i n;i )for( int j 1;j m;j ) {scanf( %d, w );ans w;num ;addEdge( S, num, w );addEdge( num, id( i, j ), inf );for( int k 0;k 4;k )if( inside( i dx[k], j dy[k] ) )addEdge( num, id( i dx[k], j dy[k] ), inf );}for( int i 1;i n;i )for( int j 1;j m;j ) {scanf( %d, w );ans w;num ;addEdge( num, T, w );addEdge( id( i, j ), num, inf );for( int k 0;k 4;k )if( inside( i dx[k], j dy[k] ) )addEdge( id( i dx[k], j dy[k] ), num, inf );}printf( %d\n, ans - dinic( S, T ) );return 0;
}
