「POI2010」桥 Bridges

我怎么就不会求欧拉回路啊啊啊啊啊啊啊啊

题目链接(LibreOJ)

看到最大的最小,首先套一个二分上去就行
二分一个答案 $x$ 之后,只连那些权值 $\le x$ 的边,这个时候的图是一张混合图,即无向边和有向边都有的图。

对于有向图或者无向图的欧拉回路很好判断,混合图的怎么搞呢?
实际上这是一个很经典的模型:首先把无向边任意定向,然后看每个点的入度和出度。因为改变一次无向边的方向可以让其中一个端点的入度 +1,出度 -1,另一个端点的入度 -1,出度 +1。回想欧拉回路存在的充要条件:所有点的出度等于入度,即:入度 – 出度 = 0。这就是网络流中的平衡条件,设立源点 S 汇点 T,S 向入度大于出度的点连容量为差值除以 2,出度大于入度的点连向 T,容量也是差值除以 2。这个图满流的时候说明欧拉回路就存在了。

然后找欧拉回路:直接 dfs 找就可以,考虑到数据对于随机的图不是很好卡,直接随机一下加边顺序即可(

这个题还有点坑:记得 check 的时候判连通性!!!

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 1050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
const int MAXN = 1050, MAXM = 20050;
struct dinic
{
    struct Edge
    {
        int to, nxt, flow, id, positive, cap;
    } e[MAXM];
    int head[MAXN], ecnt = -1, dis[MAXN], cur[MAXN];
    void add_edge(int u, int v, int f, int id)
    {
        e[++ecnt] = {v, head[u], f, id, 1, f};
        head[u] = ecnt;
        e[++ecnt] = {u, head[v], 0, id, 0, f};
        head[v] = ecnt;
    }
    int n, m, s, t;
    bool bfs()
    {
        memset(dis, 0, sizeof(dis));
        queue<int> q;
        dis[s] = 1;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt)
            {
                int v = e[i].to;
                if (!dis[v] && e[i].flow > 0)
                {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        return dis[t];
    }
    int dfs(int u, int flow)
    {
        if (u == t)
            return flow;
        int nowflow = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (dis[v] == dis[u] + 1 && e[i].flow > 0)
            {
                int tmp = dfs(v, min(flow, e[i].flow));
                e[i].flow -= tmp;
                e[i ^ 1].flow += tmp;
                flow -= tmp;
                nowflow += tmp;
                if (!flow)
                    break;
            }
        }
        return nowflow;
    }
    int solve(int n, int s, int t)
    {
        this->s = s, this->t = t, this->n = n;
        int ans = 0;
        while (bfs())
        {
            memcpy(cur, head, (n + 5) * sizeof(int));
            ans += dfs(s, inf);
        }
        return ans;
    }
    void init()
    {
        ecnt = -1;
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));
    }
} G;

int n, m, ans = -1, S, T;
struct edges
{
    int u, v, c1, c2;
    int id;
};
vector<edges> vece;
vector<pii> g[N];
int in[N], out[N];
int f[N], vis[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }

void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if (fy != fx)
        f[fy] = fx;
}

bool check(int x)
{
    G.init();
    memarray(in, 0), memarray(out, 0), memarray(vis, 0);
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (auto e : vece)
    {
        if (e.c1 <= x && e.c2 <= x)
        {
            G.add_edge(e.v, e.u, 1, e.id);
            in[e.v]++, out[e.u]++;
            Union(e.u, e.v);
        }
        else if (e.c1 <= x)
            in[e.v]++, out[e.u]++, Union(e.u, e.v);
        else if (e.c2 <= x)
            in[e.u]++, out[e.v]++, Union(e.u, e.v);
    }
    int tot = 0;
    for (int i = 1; i <= n; ++i)
    {
        int F = Find(i);
        if (!vis[F])
            vis[F] = 1, tot++;
    }
    if (tot > 1)
        return 0;
    int iniflow = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (abs(in[i] - out[i]) % 2 == 1)
            return 0;
        if (in[i] > out[i])
            G.add_edge(S, i, (in[i] - out[i]) / 2, -1), iniflow += (in[i] - out[i]) / 2;
        else if (in[i] < out[i])
            G.add_edge(i, T, (out[i] - in[i]) / 2, -1);
    }
    int maxflow = G.solve(T, S, T);
    if (maxflow != iniflow)
        return 0;
    return 1;
}

bool isadd[3050];
bool vise[N];
vector<int> vecans;
void dfsans(int u)
{
    for (auto [v, id] : g[u])
    {
        if (vise[id])
            continue;
        vise[id] = 1;
        dfsans(v);
        vecans.push_back(id);
    }
}

void workans()
{
    check(ans);
    memarray(vis, 0);
    int rk = 0;
    for (auto i : vece)
    {
        if (max(i.c1, i.c2) <= ans)
        {
            if (G.e[rk].flow < 1)
                g[i.v].push_back({i.u, i.id});
            else
                g[i.u].push_back({i.v, i.id});
            rk += 2;
            continue;
        }
        if (i.c1 <= ans)
            g[i.u].push_back({i.v, i.id});
        else if (i.c2 <= ans)
            g[i.v].push_back({i.u, i.id});
    }
    for (int i = 1; i <= n; ++i)
        random_shuffle(g[i].begin(), g[i].end());
    dfsans(1);
    reverse(vecall(vecans));
    for (auto i : vecans)
        printf("%d ", i);
}

inline void solve()
{
    scanf("%d%d", &n, &m);
    S = n + 2, T = S + 1;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, l, p;
        scanf("%d%d%d%d", &a, &b, &l, &p);
        vece.push_back((edges){a, b, l, p, i});
    }
    int l = 0, r = 1000;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    if (ans == -1)
        return puts("NIE"), void();
    printf("%d\n", ans);
    workans();
}

int main()
{
    TIME__START = clock();
    random_device rd;
    srand(rd());
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
/*
5 7
1 2 1 1
1 3 1 1
2 3 1 1
2 4 10 10
2 5 10 10
3 4 10 10
3 5 10 10

8 14
1 7 2 1
1 8 1 2
2 3 2 1
2 4 1 2
8 5 1 2
8 4 2 1
6 8 2 1
7 2 1 2
4 6 2 1
4 7 1 2
6 3 1 2
7 5 2 1
5 2 2 1
5 6 1 2
*/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注