4738.Caocao's Bridges

4738.Caocao’s Bridges

题目描述：

在赤壁之战中，曹操被诸葛亮和周瑜击败。但他不会放弃。曹操的军队仍然不善于水战，所以他提出了另一个想法。他在长江建造了许多岛屿，在这些岛屿的基础上，曹操的军队很容易攻击周瑜的部队。曹操还建造了连接岛屿的桥梁。如果所有岛屿都通过桥梁相连，那么曹操的军队可以在这些岛屿中非常方便地部署。周瑜无法忍受，所以他想要摧毁一些曹操的桥梁，这样一个或多个岛屿就会与其他岛屿分开。但周瑜只有一枚由诸葛亮留下的炸弹，所以他只能摧毁一座桥。周瑜必须派人携带炸弹来摧毁这座桥。桥上可能有守卫。轰炸队的士兵数量不能低于桥梁的守卫数量，否则任务就会失败。请弄清楚周瑜至少需要多少士兵。

就是找边权最小的桥，如果不连通的话需要输出 $0$ ；如果边权最小的桥权重为 $0$ ，需要输出 $1$ ；如果不存在桥，需要输出 $-1$ 。有重边。

数据范围：

$2\le N \le 1000, 0 \lt M \le N^2, 0\le W \le 10^4$

题解：

桥的模板题，但是会直接 WA。需要注意重边，根据 $low[v] \gt dfn[u]$ 判断桥的话会出问题。

比如 $1\rightarrow 2$ 存在重边，那么虽然满足 $low[2] \gt dfn[1]$ ，但是不是桥。因此dfs访问时需要判断第几次遇到了 fa，第一次遇到时能继续运行，第二次直接continue。

也可以使用链式前向星做法，不传入fa，直接传入边的id，id^1得到另一条对应的边。判断是不是另一条对应的边即可，这样比较精确。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<pair<int, int>> g[maxn];
int ans = INF;
int dfn[maxn], low[maxn], dfn_clock = 0;
int cnt;
void init()
{
    dfn_clock = 0;
    cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        g[i].clear();
        dfn[i] = low[i] = 0;
    }
    ans = INF;
}

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++dfn_clock;
    ++cnt;
    int times = 0;
    for (int i = 0; i < g[u].size(); ++i)
    {
        int v = g[u][i].first;
        int w = g[u][i].second;
        if (v == fa && !times)
        {
            ++times;
            continue;
        }
        if (!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
            {
                ans = min(ans, w);
            }
        }
        else
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (read(n, m), n && m)
    {
        init();
        for (int i = 1, u, v, w; i <= m; ++i)
        {
            read(u, v, w);
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }
        tarjan(1, 0);

        if (cnt != n)
            cout << 0 << endl;
        else if (ans == 0)
            cout << 1 << endl;
        else if (ans == INF)
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
    return 0;
}

void tarjan(int u, int pre)
{
    dfn[u] = low[u] = ti++;
    cnt++;
    for(int i = head[u]; i; i = ne[i])
    {
        int v = edge[i];
        if(!dfn[v])
        {
            tarjan(v, i^1);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u])
                ans = min(ans, cost[i]);
        }
        else if(i != pre)
            low[u] = min(low[u], dfn[v]);
    }
}