首页 > 其他分享 >POJ-1637 Sightseeing tour

POJ-1637 Sightseeing tour

时间:2022-10-06 23:22:56浏览次数:79  
标签:int 出度 入度 add tour POJ maxn Sightseeing out

Sightseeing tour

网络流 - 最大流

考虑欧拉图,无向边:度数全为偶数,有向边:出度和入度相等

对于有向边来说,已经不可更改;对于无向边来说,可以更改其指向

因此这题最终就是想找一种合理的方案(调整无向边的方向),使得所有点的出度等于入度

首先要判断是否是一个连通图,还要判断,所有点的度数是否为偶数,如果不满足,显然不会是欧拉图

接下来上网络流模型

对于入度大于出度的点,说明有流量要流入这个点,因此建立一个源点到该点的边,流量为 \((in[i] - out[i]) / 2\)

对于出度大于入度的点,说明这个点有流量要流出,因此建立一个该点到汇点的边,流量为 \((out[i] - in[i]) / 2\)

上述流量除以二的原因:对于 入度大于出度的点,每有 \(1\) 个无向边转向,该点的出度 \(+1\),入度 \(-1\),相当于改变了个流量;同理出度大于入度的点也是这样

假定无向边指向一个方向(假定 \(a\) 指向 \(b\)),需要建立一条从 \(b\) 到 \(a\) 的边,流量为 \(1\)

个人认为这个建模,其实就是如果有流量从一个点流出,则有一个以该点发出的有向边转向回来;流量流入一个点,则有一个指向该点的有向边转向;区别有向边和无向边就在于点与点之间的建边

最终答案满足的话,必须是网络流满流,满流才意味着每个点的出度与入度能调整到相等

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll inf = 1e17 + 10;
int head[maxn], nex[maxn], to[maxn], tp = 1, dep[maxn];
int cur[maxn];
ll vol[maxn];

int n, m, s, t;

void add(int l, int r, int w)
{
    tp++;
    nex[tp] = head[l];
    vol[tp] = w;
    to[tp] = r;
    head[l] = tp;
}

void init()
{
    for(int i=0; i<=t; i++) head[i] = 0;
    tp = 1;
}

bool bfs()
{
    queue<int>q;
    for(int i=0; i<=t; i++) dep[i] = -1;
    for(int i=0; i<=t; i++) cur[i] = head[i];
    q.push(s);
    dep[s] = 0;
    while(q.size())
    {
        int now = q.front();
        q.pop();
        for(int i=head[now]; i; i=nex[i])
        {
            int u = to[i];
            if(dep[u] != -1 || vol[i] <= 0) continue;
            dep[u] = dep[now] + 1;
            q.push(u);
        }
    }
    return dep[t] != -1;
}

ll dfs(int now, ll flow)
{
    if(now == t)
        return flow;
    ll ans = 0;
    for(int i=cur[now]; i && flow; i=nex[i])
    {
        cur[now] = i;
        int u = to[i];
        if(vol[i] <= 0 || dep[u] != dep[now] + 1) continue;
        ll f = dfs(u, min(flow, vol[i]));
        vol[i] -= f;
        vol[i ^ 1] += f;
        ans += f;
        flow -= f;
    }
    return ans;
}

ll dinic()
{
    ll ans = 0;
    while(bfs())
        ans += dfs(s, inf);
    return ans;
}

int top[maxn];
int query(int x)
{
    return top[x] == x ? x : top[x] = query(top[x]);
}

int in[maxn], out[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt;
    cin >> tt;
    while(tt--)
    {
        init();
        cin >> n >> m;
        for(int i=0; i<=n; i++) in[i] = out[i] = 0;
        int cnt = 0;
        for(int i=0; i<=n; i++) top[i] = i;
        for(int i=0; i<m; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            int aa = query(a), bb = query(b);
            if(aa != bb)
            {
                top[aa] = bb;
                cnt++;
            }
            out[a]++;
            in[b]++;
            if(c == 0)
            {
                add(b, a, 1);
                add(a, b, 0);
            }
        }
        int f = 0;
        for(int i=1; i<=n; i++)
        {
            if((in[i] + out[i]) % 2)
            {
                f = 1;
                break;
            }
        }
        if(f || cnt != n - 1)
        {
            cout << "impossible\n";
            continue;
        }
        s = n + 1;
        t = s + 1;
        cnt = 0;
        for(int i=1; i<=n; i++)
        {
            if(in[i] > out[i])
            {
                cnt += (in[i] - out[i]) / 2;
                add(s, i, (in[i] - out[i]) / 2);
                add(i, s, 0);
            }
            else if(in[i] < out[i])
            {
                add(i, t, (out[i] - in[i]) / 2);
                add(t, i, 0);
            }
        }
        ll ans = dinic();
        if(ans == cnt) cout << "possible\n";
        else cout << "impossible\n";
    }
    cout << endl;
    return 0;
}

标签:int,出度,入度,add,tour,POJ,maxn,Sightseeing,out
From: https://www.cnblogs.com/dgsvygd/p/16758815.html

相关文章

  • SPOJ6059 GCDSQF Another GCD Problem 题解
    题目大意给定两个square-freenumber\(A\)和\(B\)(即没有一个素因子的次数达到\(2\)的数)的01表示形式(即将其有无该素因子排列出来,如\(105=3\times5\times7\),则......
  • jsonschema2pojo 基于json schema 生成代码
    jsonschema2pojo是一个很不错的基于jsonschema生成代码的包以及工具(maven扩展)jsonschema2pojo特点支持基本的jsonschema操作支持java扩展,比如别名,继承扩展接口外......
  • POJ 3494 Largest Submatrix of All 1’s(单调栈)
    POJ3494LargestSubmatrixofAll1’s(单调栈)题意:​ 给出一个01矩阵,请找出其中最大的全部为1构成的子矩阵。矩阵大小为\(2000*2000\)思路:​ 我们把问题分解到每一......
  • POJ 2227 The Wedding Juicer(三维接雨水 BFS 贪心
    POJ2227TheWeddingJuicer(三维接雨水BFS贪心)题意:​ 给出一个二维地图,其各点上权值为其高度。如果向其中填水,请问在这张地图中可以积得多少水。​ 地图长宽为300,高......
  • POJ 3697 USTC campus network(BFS 删边)
    POJ3697USTCcampusnetwork(BFS删边)题意:​ 有一张图,每个点\(n\le10000\)之间都有一条边。现在删去若干条边\(m\le1000000\),请问还有多少点是联通的。思路:​ 我......
  • POJ - 2348 Euclid's Game
    Euclid'sGame博弈很经典的博弈了首先明确每个状态必然都对应着一个局面,先手必败\(or\)先手必胜如果当前局面对于先手来说是能够选择的,也就是\(b>=a*2\),对于一......
  • SPOJ GSS 系列杀青
    算是题单吧太壮观了兄弟们,可是之前\(8\)题难度评分都高一档的啊。GSS1区间最大子段和板子题,用线段树随便过。GSS2相同的数只算一次,我们离线询问,顺序插入数组中的值......
  • POJ 2348 Euclid's Game(博弈论 辗转相减)
    POJ2348Euclid'sGame(博弈论辗转相减)题目:​ 给出两个数,A,B轮流操作。每次操作可以将大的数减去小的数的整数倍,若操作后出现0,执行这次操作的人胜。思路:​ 根据样例(25......
  • POJ 1064 Cable master(浮点数二分 精度处理)
    POJ1064Cablemaster(浮点数二分精度处理)题目:​ 给出n棵木头,现在要求将木头裁成k个长度相同的小木头,请问这k个小木头的最大长度是多少。裁出来后不支持拼接。所有长度......
  • POJ 2247 Humble Numbers(搜索,生成子集)
    HumbleNumbers(搜索,生成子集)题目:​ 给出多次询问,问第k个丑数是多少(最多询问到k=5842)。​ 丑数:分解质因数后,质因子只包含2,3,5,7的数字。思路:​ 通过预处理得到,584......