statement
给你一个 (n) 个点 (m) 条边的无向图,边有权值,要求你删去最多两条边,使得 (s) 与 (t) 不连通,且删去的边权值和最小。
Hints
(2le nle 1000) ,(0le m le 30000)
solution
首先考虑删除一条边的情况,必定是有一条从 (s) 到 (t) 的所有路径中,都经过的一条边,随便找一条路径枚举即可,时间复杂度 (mathcal O (n imes m)) 。
两条路径的情况就是把一条边删去后,又出现了一条如上述的边,而直接枚举两条边的复杂度是 (mathcal O (m ^ 3)) 的,通过 tarjan
算法判桥可以做到 (mathcal O (m ^ 2)) 。
很容易发现,这样枚举是有完全不可能合法的方案的,运用人类智慧,发现在同一条 (s ightarrow t) 的路径上必定有一条边是会被删去的。
所以直接先拉出任意一条路径,直接暴力枚举即可,时间复杂度 (mathcal O (n imes m)) 。
struct Lst {
int dir, nxt, w;
Lst() {}
Lst(int _d, int _n, int _w) : dir(_d), nxt(_n), w(_w) {}
} E[M << 1];
int G[N], cnt = 1;
inline void Add(int u, int v, int w) {E[++cnt] = Lst(v, G[u], w), G[u] = cnt;}
int n, m, s, t, ban, dfn[N], ord, brg[M], vis[M], vt[M], lst[N], res = 2e9 + 1;
vector<int> pth;
void path(int u) {
vis[u] = 1; if(u == t) return ;
for(register int i=G[u], v; i; i=E[i].nxt) if(i != ban && i != (ban ^ 1)) {
v = E[i].dir;
if(vis[v]) continue ;
lst[v] = i, path(v);
}
}
int tarjan(int u) {
int low = dfn[u] = ++ord, lowv;
for(register int i=G[u], v; i; i=E[i].nxt) if(!vt[i]) {
v = E[i].dir, vt[i] = vt[i ^ 1] = 1;
if(!dfn[v]) {
low = min(low, lowv = tarjan(v));
if(lowv > dfn[u]) {
brg[i >> 1] = 1;
}
} else if(dfn[v] < dfn[u]) low = min(low, dfn[v]);
}
return low;
}
int ansl, ansr;
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
forn(i,1,m) {
static int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w), Add(v, u, w);
}
ban = 1e9, path(s);
if(!vis[t]) return printf("0
0
") & 0;
int tmp = t;
while(tmp != s) pth.push_back(lst[tmp]), tmp = E[lst[tmp] ^ 1].dir;
ansl = ansr = -1;
rep(i,0,pth.size()) {
ban = pth[i], ord = 0;
memset(dfn, 0, sizeof dfn);
memset(brg, 0, sizeof brg);
memset(vis, 0, sizeof vis);
memset(lst, 0, sizeof lst);
memset(vt, 0, sizeof vt);
vt[pth[i]] = vt[pth[i] ^ 1] = 1;
path(s);
if(!vis[t]) {
if(res > E[pth[i]].w) res = E[pth[i]].w, ansl = pth[i], ansr = -1;
} else {
tarjan(s), tmp = t;
while(tmp != s) {
int e = lst[tmp];
if(brg[e >> 1]) if(res > E[pth[i]].w + E[e].w)
res = E[pth[i]].w + E[e].w, ansl = pth[i], ansr = e;
tmp = E[e ^ 1].dir;
}
}
}
if(res == 2e9 + 1) return puts("-1") & 0;
if(ansr == -1) {
printf("%d
1
", res);
printf("%d
", ansl >> 1);
} else {
printf("%d
2
", res);
printf("%d %d
", ansl >> 1, ansr >> 1);
}
return 0;
}