创意活动策划网站,久久建筑网怎么赚金币,中山推广网站,做免费资料分享网站会不会涉及版权正题
题目链接:http://pjudge.ac/contest/951/problem/21655 题目大意
给出一张nnn个点的简单无向图#xff0c;每条边的两个方向具有不同权值。求一个权值和最小的定向方案使得整张图强连通。 1≤n≤18,−1≤ai,j≤1061\leq n\leq 18,-1\leq a_{i,j}\leq 10^61≤n≤18,−1≤…正题
题目链接:http://pjudge.ac/contest/951/problem/21655 题目大意
给出一张nnn个点的简单无向图每条边的两个方向具有不同权值。求一个权值和最小的定向方案使得整张图强连通。
1≤n≤18,−1≤ai,j≤1061\leq n\leq 18,-1\leq a_{i,j}\leq 10^61≤n≤18,−1≤ai,j≤106 解题思路
考虑一个朴素的想法我们dpdpdp出一条从111出发经过所有点的路径然后这条路径上的边强制定向其他的边随意定向。
发现这个想法的难点在于一条边重复经过会统计多次和其他边的随意定向的权值。
先考虑其他边随意定向的权值这个很好解决对于每条边我们先默认定向为权值较小的方向然后这个方向的权值就变成000而另一个方向的权值减去这个权值。
这样如果一条边没有被经过就可以不用重复定向了。
然后考虑解决重复统计的问题我们考虑另一种扩展方式假设目前点集SSS都在强连通分量内我们找到一条路径x→yx\rightarrow yx→y其中x,y∈Sx,y\in Sx,y∈S这样路径上的所有点都会被融入点集SSS内。
那么我们设fS,x,yf_{S,x,y}fS,x,y表示点集SSS强连通的情况下目前我们在找一条路径终点是xxx目前走到yyy是的最小定向权值。
需要注意的是一条边只能被定向一次所以需要特殊转移。
时间复杂度O(2nn3)O(2^nn^3)O(2nn3) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N18,inf2147483647/3;
int n,a[N][N],f[1N][N][N],g[1N],ans;
int main()
{scanf(%d,n);for(int i0;in;i)for(int j0;jn;j)scanf(%d,a[i][j]);for(int i0;in;i)for(int ji1;jn;j){if(a[i][j]!-1){int xmin(a[i][j],a[j][i]);ansx;a[i][j]-x;a[j][i]-x;}}memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));int MS1n;g[1]0;for(int s0;sMS;s){if(!(s1))continue;if(sMS-1)ansg[s];if(g[s]inf){for(int i0;in;i){if(!((si)1))continue;for(int j0;jn;j){if((sj)1)continue;for(int k0;kn;k){if(!((sk)1)||a[k][j]-1)continue;if(ki)f[s|(1j)][i][j]min(f[s|(1j)][i][j],g[s]a[k][j]);else f[s][i][j]min(f[s][i][j],g[s]a[k][j]);}}}}for(int x0;xn;x){if(!((sx)1))continue;for(int i0;in;i){if(f[s][x][i]inf)continue;for(int j0;jn;j){if(((sj)1)||a[i][j]-1)continue;f[s|(1i)][x][j]min(f[s|(1i)][x][j],f[s][x][i]a[i][j]);}}}for(int x0;xn;x){if(!((sx)1))continue;for(int i0;in;i){if(f[s][x][i]inf)continue;for(int j0;jn;j){if(((sj)1)||a[i][j]-1)continue;f[s|(1i)][x][j]min(f[s|(1i)][x][j],f[s][x][i]a[i][j]);}}}for(int i0;in;i){if(!((si)1))continue;for(int j0;jn;j){if((sj)1||a[j][i]-1)continue;g[s|(1j)]min(g[s|(1j)],f[s][i][j]a[j][i]);}}}if(ansinf)puts(-1);else printf(%d\n,ans);return 0;
}
