惠州规划建设局网站,网站前台架构,如何搭建一个网站平台,wordpress添加会员标识problem
给定 nnn 个数 {ai}\{a_i\}{ai}#xff0c;其中 kkk 个 aia_iai 是奇数#xff0c;再给一个 nnn\times nnn 的矩阵 {ci,j}\{c_{i,j}\}{ci,j}#xff0c;无论是 aaa 还是 ccc#xff0c;都保证是非负整数。
现在可以做一类操作#xff1a;将 ai−1,aj−1a_…problem
给定 nnn 个数 {ai}\{a_i\}{ai}其中 kkk 个 aia_iai 是奇数再给一个 n×nn\times nn×n 的矩阵 {ci,j}\{c_{i,j}\}{ci,j}无论是 aaa 还是 ccc都保证是非负整数。
现在可以做一类操作将 ai−1,aj−1a_i-1,a_j-1ai−1,aj−1花费 ci,jc_{i,j}ci,j 代价i,ji,ji,j 可以相同。
要求把所有的 {ai}\{a_i\}{ai} 全都变为 000。
求最小花费无解输出 −1-1−1。
n≤50,k≤8n\le 50,k\le 8n≤50,k≤8保证 ci,jcj,ic_{i,j}c_{j,i}ci,jcj,i。
solution
显然每次操作都会使得 (∑ai)−2(\sum a_i)-2(∑ai)−2。所以如果 ∑ai\sum a_i∑ai 是奇数即 aia_iai 为奇数的 iii 有奇数个则无解。
接下来再来解决有解的问题。
先考虑 k0k0k0 的弱化版。
那就存在欧拉回路要求每个点的入度和出度相同经典网络流模型转化。
将每个点拆成两个点各放左右部与源/汇点的连边流量设置为 ai2\frac{a_i}22ai。
花费针对“关系”而言左右部点之间连边流量无穷带花费。
直接跑最小费用流即可。 转化思考 如果操作 i,ji,ji,j就在图上连一条 (i,j)(i,j)(i,j) 的边。那么最后这张图可能有重边和若干个环。 发现这是一张欧拉图存在欧拉回路。我们能找到一种定向方式使得每个点的入度和出度相同。 推出存在一种最优方案使得每个点的入度和出度相同。 将每个点拆成入度点和出度点转化成匹配问题。 现在有几个特殊点是奇数欧拉回路不存在变成存在欧拉路径。
我们先通过若干次操作将这些奇数全都消成偶数就又转化成了欧拉回路就可以套用上面的方法。 转化思考 我们通过对图上进行加边使得这张图最后仍是存在欧拉回路的图。 由此推出存在一种最优方案使得奇数点的入度和出度只相差 111。 由于 kkk 非常小我们大可直接状压枚举哪一半的奇数点是入度多 111剩下的就肯定是出度多 111。
还是转化成了入度和出度二分图的匹配问题仍然跑个最小费用流。
最后求个 min\minmin 就完了。
code
#include bits/stdc.h
using namespace std;
#define maxn 200
#define inf 0x7f7f7f7f
struct node { int to, nxt, flow, cost; }E[maxn * maxn];
int head[maxn], dis[maxn], lst[maxn], a[maxn], b[maxn], id[maxn];
int c[maxn][maxn];
bool vis[maxn];
int n, cnt, m, s, t;
queue int q;void addedge( int u, int v, int flow, int cost ) {E[ cnt] { v, head[u], flow, cost }, head[u] cnt;E[ cnt] { u, head[v], 0, - cost }, head[v] cnt;
}bool SPFA() {memset( lst, -1, sizeof( lst ) );memset( dis, 0x7f, sizeof( dis ) );dis[s] 0, q.push( s );while( ! q.empty() ) {int u q.front(); q.pop(); vis[u] 0;for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( dis[v] dis[u] E[i].cost and E[i].flow ) {dis[v] dis[u] E[i].cost; lst[v] i;if( ! vis[v] ) vis[v] 1, q.push( v );}}}return ~ lst[t];
}int solve() {memset( head, -1, sizeof( head ) ), cnt -1;for( int i 1;i n;i )for( int j 1;j n;j )addedge( i, j n, inf, c[i][j] );for( int i 1;i n;i ) {addedge( s, i, a[i] b[i] 1, 0 );addedge( i n, t, a[i] - b[i] 1, 0 );}int ans 0;while( SPFA() ) {int flow inf;for( int i lst[t];~ i;i lst[E[i ^ 1].to] )flow min( flow, E[i].flow );ans flow * dis[t];for( int i lst[t];~ i;i lst[E[i ^ 1].to] ) {E[i ^ 1].flow flow;E[i].flow - flow;}}return ans;
}int main() {scanf( %d, n ); s 0, t n 1 | 1;for( int i 1;i n;i ) {scanf( %d, a[i] );if( a[i] 1 ) id[m ] i;}for( int i 1;i n;i )for( int j 1;j n;j )scanf( %d, c[i][j] );if( m 1 ) return ! puts(-1);int ans inf;for( int i 0;i (1 m);i ) {for( int j 0;j m;j )if( i j 1 ) b[id[j]] 1;else b[id[j]] -1;if( __builtin_popcount( i ) ^ (m 1) ) continue;ans min( ans, solve() );}printf( %d\n, ans );return 0;
}
