网站建设报价费用是多少,台州 网站建设,公司内部网站源码,wordpress增加登陆功能题解#xff1a; 一道比较水的题 但这个测试数据极弱我也不知道我的代码正确性是不是有保证 构成一个边双联通 可以由两个有一个公共点的边双联通或者一个边双加一条链构成 所以我们需要要预处理出所有环 令f[i][j][k]表示起点为i#xff0c;终点为j#xff0c;经过点的状态…题解 一道比较水的题 但这个测试数据极弱我也不知道我的代码正确性是不是有保证 构成一个边双联通 可以由两个有一个公共点的边双联通或者一个边双加一条链构成 所以我们需要要预处理出所有环 令f[i][j][k]表示起点为i终点为j经过点的状态为k,这样递推 那么最后环就是加上j-i这条边就可以了 但是注意一个二元环一个为最长边一个为次长边 其他环都不会用到次长边 代码 #include bits/stdc.h
using namespace std;
#define IL inline
#define rint register int
#define dep(i,t,h) for (rint it;ih;i--)
#define rep(i,h,t) for (rint ih;it;i)
char ss[124],*Ass,*Bss;
IL char gc()
{return AB(B(Ass)fread(ss,1,124,stdin),AB)?EOF:*A;
}
templateclass Tvoid read(T x)
{rint f1,c; while (cgc(),c48||c57) if (c-) f-1; x(c^48);while(cgc(),c47c58) x(x3)(x1)(c^48); x*f;
}
void umin(int x,int y)
{if (xy) xy;
}
int dp[15][15][114],ff[114],f[20][20][2],n,m;
bool tf[114];
const int INF1e9;
int main()
{int T;read(T);rep(tt,1,T){read(n); read(m);rep(i,1,n) rep(j,1,n)f[i][j][0]f[i][j][1]INF;rep(i,1,m){int x,y,z;read(x); read(y); read(z);if (zf[x][y][0]) f[x][y][1]f[x][y][0],f[x][y][0]z,f[y][x][1]f[y][x][0],f[y][x][0]z;else if (zf[x][y][1]) f[x][y][1]z,f[y][x][1]z;}rep(i,1,n)rep(j,1,n)rep(k,1,(1n)-1) dp[i][j][k]INF;rep(i,1,n) dp[i][i][(1(i-1))]0;rep(i,1,(1n)-1){int a[100];int cnt0;rep(j,1,n)if ((i(j-1))1) a[cnt]j;rep(i1,1,cnt)rep(j1,1,cnt)rep(k,1,n)if (!((i(k-1))1))umin(dp[a[i1]][k][i|(1(k-1))],dp[a[i1]][a[j1]][i]f[a[j1]][k][0]);}rep(i,1,(1n)-1) tf[i]0;rep(i,1,(1n)-1) ff[i]INF;rep(i,1,n)rep(j,1,n)if (i!j)tf[(1(i-1))(1(j-1))]1,ff[(1(i-1))(1(j-1))]min(INF,f[i][j][0]f[i][j][1]);rep(i,1,(1n)-1)if (!tf[i])rep(j,1,n)rep(k,1,n)umin(ff[i],dp[j][k][i]f[j][k][0]);rep(i,1,(1n)-1)for (int ji;j;ji(j-1))rep(k,1,n)if (j(1(k-1)))umin(ff[i],ff[(i^j)|(1(k-1))]ff[j]);if (ff[(1n)-1]!INF) coutff[(1n)-1]endl;else coutimpossibleendl; }return 0;
} 转载于:https://www.cnblogs.com/yinwuxiao/p/9317508.html
