建设工程招投标网最专业的网站,如何做一个商城类型的网站,蝙蝠侠大连网络营销,网站建设论文 优帮云正题
题目链接:https://loj.ac/p/3320 题目大意
有一张nnn个点的无向完全图#xff0c;每一条边是红色或者蓝色#xff0c;对于每个点sss求从这个点出发的一条尽量短的经过所有点的路径。 1≤n≤20001\leq n\leq 20001≤n≤2000 解题思路
显然地猜测一下最短的长度肯定是n…正题
题目链接:https://loj.ac/p/3320 题目大意
有一张nnn个点的无向完全图每一条边是红色或者蓝色对于每个点sss求从这个点出发的一条尽量短的经过所有点的路径。
1≤n≤20001\leq n\leq 20001≤n≤2000 解题思路
显然地猜测一下最短的长度肯定是nnn说是找一条路径实际上我们是能够找到一个颜色交替只有一次的环的然后交替位置就在sss的旁边。
我们构造一下此时有两条不相交的路径s→x,t→ys\rightarrow x,t\rightarrow ys→x,t→y并且两条路径上颜色都相同一条红色一条蓝色。
我们假设s→xs\rightarrow xs→x的路径是红色此时对于一个未加入的点zzz如果(x,z)(x,z)(x,z)是红色或者(y,z)(y,z)(y,z)是蓝色那么直接加长路径即可。
否则也就是说(x,z)(x,z)(x,z)是蓝色且(y,z)(y,z)(y,z)是红色我们考虑(x,y)(x,y)(x,y)之间的路径颜色假设是红色那么如图 我们将yyy弹出路径t→yt\rightarrow yt→y然后加入s→xs\rightarrow xs→x后就可以再加入zzz了。
如果是蓝色同理弹另一边。
但是此时会出现两种情况
蓝色路径弹出后为空了那么此时我们再找一个新的点当做新的ttt即可反正我们的要求是sss不变。红色路径弹出后为空了那么此时我们将zzz作为新的ttt然后原本的s→ts\rightarrow ts→t路径变为s→xs\rightarrow xs→x路径。
时间复杂度O(n2)O(n^2)O(n2) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N2100;
int n,G[N][N];
char s[N];
vectorintl,r;
int main()
{scanf(%d,n);if(n2){printf(2\n1 2\n2\n2 1\n);return 0;}for(int i2;in;i){scanf(%s,s1);for(int j1;ji;j)G[i][j]G[j][i](s[j]R);}for(int s1;sn;s){int zs%n1,g0;l.clear();r.clear();l.push_back(z);r.push_back(s);gG[s][z%n1];for(int xz%n1;x!s;xx%n1){if(G[r[r.size()-1]][x]g)r.push_back(x);else if(G[l[l.size()-1]][x]!g)l.push_back(x);else{if(G[l[l.size()-1]][r[r.size()-1]]g){r.push_back(l[l.size()-1]);r.push_back(x);l.pop_back();if(!l.size()){xx%n1;if(xs)break;l.push_back(zx);}}else{l.push_back(r[r.size()-1]);l.push_back(x);r.pop_back();if(!r.size()){l.pop_back();l.swap(r);l.push_back(x);zx;g!g;}}}}printf(%d\n,n);for(int i0;ir.size();i)printf(%d ,r[i]);for(int il.size()-1;i0;i--)printf(%d ,l[i]);putchar(\n);}return 0;
}
