vs 手机网站开发,广告软文范例200字,台州建设银行官方网站,宠物网站建设策划方案2756: [SCOI2012]奇怪的游戏 Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 2571 Solved: 685[Submit][Status][Discuss]Description Blinker最近喜欢上一个奇怪的游戏。 这个游戏在一个 N*M 的棋盘上玩#xff0c;每个格子有一个数。每次 Blinker 会选择两个相邻的格子每个格子有一个数。每次 Blinker 会选择两个相邻的格子并使这两个数都加上 1。 现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数如果永远不能变成同一个数则输出-1。 Input 输入的第一行是一个整数T表示输入数据有T轮游戏组成。 每轮游戏的第一行有两个整数N和M 分别代表棋盘的行数和列数。 接下来有N行每行 M个数。 Output 对于每个游戏输出最少能使游戏结束的次数如果永远不能变成同一个数则输出-1。 Sample Input 2 2 2 1 2 2 3 3 3 1 2 3 2 3 4 4 3 2 Sample Output 2 -1 HINT 【数据范围】 对于30%的数据保证 T101N,M8 对于100%的数据保证 T101N,M40所有数为正整数且小于1000000000 考虑末状态有所有数都相等的很好性质所以设所有数的变为x。因为每次只会对相邻两个格子加1所以奇偶分治后两种格子的变化量相同。 所以可以列出方程 这里借用黄学长的博客 对棋盘进行黑白染色设黑格个数为num1 数值和为sum1设白格个数为num1 数值和为sum1 设最后都变为x则num1 * x – sum1 num2 * x – sum2x (sum1 – sum2) / (num1 – num2) 然后分类讨论 当num1 ≠ num2时 可以解出 x 再用网络流check即可 对于num1 num2时 可以发现 对于一个合法的x kx都是一个合法的解因为num1 num2 (num1 num2) % 2 0 可以构造一层的满覆盖所以可以二分x 然后用网络流check 建图如果点k为白建边(s, k, x – v[k])如果为黑建边(k, t, x – v[k])对相邻点u、v (u为白)建边 (u, v, inf) 方法利用末状态性质设未知数列出方程。然后分类讨论首先要满足方程才有解然后可以二分答案在check。其实如果都合法可以直接二分末状态然后check。方程讨论是因为解得情况在不同条件下不同。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
#define maxn 2020
#define maxm 8020
#define INF 100000000000000lltypedef long long LL;
struct node{int next,to;LL f;
}e[maxm * 2];
int head[maxn],cnt 1,src,sink;
int q[maxn],hh,tt,dis[maxn],cur[maxn];
int n,m,T,num1,num2,mx;
LL sum1,sum2,maxflow,x,ans;
int dt[maxn][maxn];inline void adde(int x,int y,LL c){e[cnt].to y;e[cnt].next head[x];e[cnt].f c;head[x] cnt;e[cnt].to x;e[cnt].next head[y];head[y] cnt;
}
inline bool bfs(){tt hh 0;memset(dis,0,sizeof(dis));q[tt] src , dis[src] 1;while ( hh tt ){int now q[hh];for (int i head[now] ; i ; i e[i].next){if ( e[i].f !dis[e[i].to] ){q[tt] e[i].to;dis[e[i].to] dis[now] 1;}}}return dis[sink] 0;
}
LL dfs(int now,LL delta){if ( now sink || !delta ) return delta;LL ret 0;for (int i cur[now] ; i ; i e[i].next){if ( e[i].f dis[now] 1 dis[e[i].to] ){LL d dfs(e[i].to,min(delta,e[i].f));ret d , delta - d;e[i].f - d, e[i ^ 1].f d;if ( !delta ) return ret;}}if ( delta ) dis[now] -1;return ret;
}
inline LL dinic(){LL flow 0;while ( bfs() ){for (int i 1 ; i sink ; i) cur[i] head[i];flow dfs(src,INF);}return flow;
}
inline void init(LL x){memset(head,0,sizeof(head));memset(e,0,sizeof(e));cnt 1;for (int i 1 ; i n ; i){for (int j 1 ; j m ; j){if ( (i j) 1 ){adde((i - 1) * m j,sink,x - (LL)dt[i][j]);}else{int now (i - 1) * m j;adde(src,(i - 1) * m j,x - (LL)dt[i][j]);if ( i 1 ) adde(now,now - m,INF);if ( i n ) adde(now,now m,INF);if ( j 1 ) adde(now,now - 1,INF);if ( j m ) adde(now,now 1,INF);}}}
}
int main(){freopen(input.txt,r,stdin);scanf(%d,T);while ( T-- ){ans sum1 sum2 0 , mx num1 num2 0;scanf(%d %d,n,m);src n * m 1 , sink n * m 2;for (int i 1 ; i n ; i){for (int j 1 ; j m ; j){scanf(%d,dt[i][j]);if ( (i j) 1 ) sum2 (LL)dt[i][j] , num2;else sum1 (LL)dt[i][j], num1;mx max(dt[i][j],mx);}}if ( num1 ! num2 ){if ( ((sum1 - sum2) % (LL)(num1 - num2)) ! 0 ){printf(-1\n);continue;} x (sum1 - sum2) / (LL)(num1 - num2);if ( x mx ){printf(-1\n);continue;}init(x);maxflow dinic();if ( maxflow sum1 (LL)num1 * x ){printf(%lld\n,maxflow);}else printf(-1\n);}else{LL l mx , r INF;//二分把当前的每个数都变成mid的情况for (int i 1 ; i 50 ; i){maxflow 0;LL mid (l r) 1;init(mid);maxflow dinic();if ( maxflow sum1 (LL) num1 * mid ){ans maxflow , r mid;}else l mid 1;}if ( !ans ) printf(-1\n);else printf(%lld\n,ans);}}return 0;
} 转载于:https://www.cnblogs.com/zqq123/p/5263783.html
