2023寒假图论练习

标签：图论 const int ll dis 寒假 2023 include define

k.Killer Sajin's Matrix

https://ac.nowcoder.com/acm/contest/38727/K

题意

构造一个n*m的01矩阵使得1的个数正好是k，每行每列的和为奇数

思路

我们可以把这个问题转化成一个经典图论问题。
这就相当于对于某个位置是1的，我们就把那一行和那一列连一条边。然后因为限制就是，每行每列的度数为奇数，且所有行度数和为k,所有列度数和为k，那我们就可以先给每行每列都度数为1，然后根据k还剩余的度数，两个两个分给一行或一列。
无法构造的情况就是：一开始无法给每个点都分配一个度数或者后面两个两个分，分到最后只剩一个无法凑两。
这样我们每个行和列都有一个度数了，那我们就可以二分图构造。将行的度数从大到小排列，如果当前行要x个度数，那我们就让他与剩余度数最大的x个列连边，这样一定能保证有解。

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 1e7 + 5;

int n, m, k;
int cnt[N], cnt2[N];
void solve() {
    cin >> n >> m >> k;
    if(k < n || k < m){
        cout << "No\n";
        return;
    }

    for(int i = 1; i <= n; i++)
        cnt[i] = 1;
    for(int i = 1; i <= m; i++)
        cnt2[i] = 1;
    int k1 = k - n;
    int k2 = k - m;
    if(k1 % 2 || k2 % 2) {
        cout << "No" << "\n";
        return;
    }

    for(int i = 1; k1; i++){
        if(i > n) i = 1;
        cnt[i] += 2;
        k1 -= 2;
    }

    for(int i = 1; k2; i++){
        if(i > m) i = 1;
        cnt2[i] += 2;
        k2 -= 2;
    }

    // for(int i = 1; i <= n; i++)
    //     cerr << cnt[i] << " \n"[i == n];
    // for(int i = 1; i <= m; i++)
    //     cerr << cnt2[i] << " \n"[i == m];

    vector<pair<int, int>>ans;
    priority_queue<pair<int, int>>q;
    for(int i = 1; i <= m; i++)
        q.push({cnt2[i], i});
       
    for(int i = 1; i <= n; i++){
        vector<int>ve;
        for(int j = 1; j <= cnt[i]; j++){
            if(q.empty()){
                cout << "No" << "\n";
                return;
            }

            auto [x, id] = q.top();
            q.pop();
            cnt2[id]--;
            ans.push_back({i, id});
            if(cnt2[id]) ve.push_back(id);
            
        }
        
        for(auto& id : ve)
            q.push({cnt2[id], id});
    }

    cout << "Yes\n";
    for(auto& [u, v] : ans)
        cout << u << " " << v << "\n";
}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	IOS;
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

E. Anya's Simultaneous Exhibition

https://codeforces.ml/contest/1779/problem/E

题意

n个人，谁能打败谁是固定的，一次比赛选两个人对决，输的淘汰，最后留下那个是赢者。
每次可以询问一个i和另外若干个人比赛的胜负情况，你要找到最后可能获胜的几个人。
询问次数不能超过2*n.

思路

其实这就是一张竞赛图，我们可以询问两两的胜负情况，然后构建出一张竞赛图。
然后根据竞赛图的性质，按出度排列，找到第一个强连通分量就是所有可能获胜的人。

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e7 + 5;
int out[N], n, c[N];
pair<int, int>p[N];

void query(int x) {
    string s = "";
    for (int i = 1; i <= n; i++) {
        if (i == x) s += '0';
        else s += '1';
    }
    cout << "? " << x << " " << s << "\n";
    cout.flush();
    cin >> out[x];
}

void solve() {
    cin >> n;
    //cout << 1 << "\n";
    //cout.flush();
    for (int i = 1; i <= n; i++) {
        query(i);
        p[i] = { out[i], i };
    }
    sort(p + 1, p + 1 + n, greater<>());

    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += p[i].first;
        c[p[i].second] = 1;
        int num = i * (i - 1) / 2 + i * (n - i);
        if (sum == num) {
            string ans = "";
            for (int j = 1; j <= n; j++) {
                if (c[j]) ans += '1';
                else ans += '0';
            }
            cout << "! " << ans << "\n";
            cout.flush();
            return;
        }
    }

}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
    //IOS;
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}

J. Perfect Matching

https://codeforces.ml/gym/104128/problem/J

题意

给定n个点的无向图，如果两个点满足\(|a_i - a_j| = |i - j|\) 就将两个点连一条边。
然后求这个无向图的完美匹配。

思路

我们可以将这个绝对值拆分，条件变成 \(a_i + i = a_j + j\) 或 \(a_i - i = a_j - j\),然后转化成图论问题。
转化成二分图，将\(a_i - i\)作为二分图左边的点，\(a_i + i\)为右边的点，对于每个\(a_i\)我们让 \(a_i - i\)到\(a_i + i\)连边，这条边就代表是原来的点i。
如果两条边有公共点，说明两条边（即原来的两个点）可以匹配，这样就变成了求二分图上，邻边匹配问题。
这个邻边匹配问题比较典型，我们可以先找出一颗生成树，然后让某个点的儿子两两匹配，如果还多出一个儿子就和父亲匹配，如果是非树边，也可以类似操作。

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 5;
const int M = 1e7 + 5;

int n, a[N], used[N], vis[N], f, tot;
vector<pair<int, int>>g[N];
vector<pair<int, int>>ans;
map<int, int>mp, mp2;

void dfs(int x, int id){
    vector<int>ve;
    vis[x] = 1;
    for(auto& [to, id2] : g[x]){
        if(id == id2) continue;
        if(!vis[to]) dfs(to, id2);
        if(!used[id2])
            ve.push_back(id2);
    }

    int m = ve.size();
    if(m % 2) {
        if(id == -1){
            f = 1;
            return;
        }

        for(int i = 0; i < m - 1; i += 2) {
            ans.push_back({ve[i], ve[i + 1]});
            used[ve[i]] = 1;
            used[ve[i + 1]] = 1;
        }
        ans.push_back({ve[m - 1], id});
        used[ve[m - 1]] = 1;
        used[id] = 1;
    }
    else{
        for(int i = 0; i < m; i += 2) {
            ans.push_back({ve[i], ve[i + 1]});
            used[ve[i]] = 1;
            used[ve[i + 1]] = 1;
        }
    }
}

void init(){
    mp.clear();
    mp2.clear();
    for(int i = 1; i <= n * 2; i++) {
        g[i].clear();
        vis[i] = 0;
    }
    for(int i = 1; i <= n; i++)
        used[i] = 0;
    ans.clear();
}

void solve() {
    cin >> n;
    init();
    
    tot = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        int u = a[i] - i;
        int v = a[i] + i;
        if(mp.count(u) == 0) {
            mp[u] = ++tot;
            u = tot;
        }
        else u = mp[u];

        if(mp2.count(v) == 0) {
            mp2[v] = ++tot;
            v = tot;
        }
        else v = mp2[v];

        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
     
    f = 0;
    for(int i = 1; i <= n; i++){
        int s = mp[a[i] - i];
        if(!vis[s]) 
            dfs(s, -1);
        if(f) {
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";
    for(auto& [u, v] : ans)
        cout << u << " " << v << "\n";

}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	IOS;
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

E - GCD of Path Weights

https://atcoder.jp/contests/arc144/tasks/arc144_e

题意

给定一个dag,给每个点设点权，使得1号点到n号点的所有路径的点权的gcd，存在有些点权值未知。

思路

先考虑有边权求1到n所有路径权值的gcd这个典型问题。
对于这个问题，我们可以先把1不能到达的点和n不能到达的点给去掉，然后构成一个新的图。
对于这个图，我们可以先将他看成一颗生成树，将1点标记为0。然后我们就沿着树边，将每个点根据边权标记好（设i点标记为dis[i]）。
然后问题就变成了求最大的p使得p能整除dis[0]和dis[n]，且对于每条非树边[u, v, w]，p能整除\(|dis[v] - (dis[u] + w)|\)。即就是求这些值的gcd。

再回过来看这个问题，因为是点权，所以我们其实可以将每个点拆成两个点，这两个点(出点入点)连一条权值为\(a_i\)的边，然后再根据原图，让u的出点和v的入点连一条权值为0的边。
如果是权值未知的点那我们就不给它的出入点连边。因为有可能存在断开的情况所以我们连的应该是无向边。
然后再按上面一样的做法求答案就可。(注意的是因为有权值未知点的存在，可能有多个连通图，应该遍历每个求答案)

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 6e5 + 5;
const int M = 1e6 + 5;

int n, m, a[N], c[2][N], val[N], vis[N], ans;
int can[N];
vector<int>g[2][N];
vector<pair<int, int>>g2[N];
pair<int, int>e[N];

void dfs(int x, int k){
    c[k][x] = 1;
    for(auto to : g[k][x]) {
        if(c[k][to]) continue;
        dfs(to, k);
    }
}

void dfs2(int x){
    vis[x] = 1;
    for(auto [to, w] : g2[x]){
        if(!vis[to]) {
            val[to] = val[x] + w;
            dfs2(to);
        }
        else ans = gcd(ans, abs(val[x] + w - val[to]));
    }
}

void solve() {
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        g[0][u].push_back(v);
        g[1][v].push_back(u);
        e[i] = {u, v};
    }

    for(int i = 1; i <= n; i++)
        cin >> a[i];

    dfs(1, 0);
    dfs(n, 1);
    if(!c[0][n]) {
        cout << "-1\n";
        return;
    }

    for(int i = 1; i <= n; i++){
        if(c[0][i] && c[1][i]) {
            if(a[i] != -1) {
                g2[i].push_back({i + n, a[i]});
                g2[i + n].push_back({i, -a[i]});
            }
            can[i] = 1;
        }
    }

    for(int i = 1; i <= m; i++){
        int u = e[i].first;
        int v = e[i].second;
        if(can[u] && can[v]) {
            g2[u + n].push_back({v, 0});
            g2[v].push_back({u + n, 0});
        }
    }

    ans = 0;
    for(int i = 1; i <= n * 2; i++){
        if(!vis[i]) {
            val[i] = 0;
            dfs2(i);
            if(i == 1 && vis[n + n]) //样例四的情况
                ans = gcd(ans, val[n + n]);
        }
    }

    if(!ans) {
        cout << -1 << "\n";
        return;
    }
    cout << ans << "\n";
}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

G - Farthest City

https://atcoder.jp/contests/abc281/tasks/abc281_g

题意

给定n个点求构造 1节点到其他所有节点的最短路中，1到n的最短路最大的无向连通图的方案数。

思路

可以联系bfs树，每一层节点到源点的距离相同，一条边的两个的到源点的距离差值不超过1。
我们可以一层一层构造，然后dp计数。
dp[i][j]代表前i个点，最后一层有j个点的方案数。
那么dp[i][j]就是从上一层转移过来的让k代表上一层的点数，我们就可以枚举k来转移，即dp[i - j][k]->dp[i][j]。
然后就是求方案数，对于当前最后一层的j个点，两两之间都可以选择连边或者不连边即有\(2^{((^j_2))}\)种方案，然后对于j个点中的一个点，它可以跟前面k个点任意几个连边或不连边，但不能全不连边，那么这部分的方案数就是\((2^k - 1)^j\),然后这j个点的选法有\((^{n - i + j - 1}_j)\)的方案
三部分相乘就是每次转移多的方案复杂度O(n^3)

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 500 + 5;
const int M = 1e6 + 5;

int n, m;
int c[N][N], dp[N][N];
int pow2[M];

int qpow(int base, int pow){
    int ans = 1;
    while(pow){
        if(pow & 1) ans = ans * base % m;
        base = base * base % m;
        pow >>= 1;
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    //预处理组合数和幂指数不然会超时
    for(int i = 1; i <= n; i++)
        c[i][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % m;
        c[i][i] = 1;
    }

    pow2[0] = 1;
    for(int i = 1; i <= n * n; i++)
        pow2[i] = pow2[i - 1] * 2 % m;

    dp[1][1] = 1;
    for(int i = 2; i < n; i++){
        for(int j = 1; j <= i - 1; j++){
            for(int k = 1; k <= i - j; k++){
                dp[i][j] = (dp[i][j] + dp[i - j][k] * pow2[c[j][2]] % m * qpow((pow2[k] - 1 + m) % m, j) % m * c[n - i + j - 1][j] % m) % m;
            }
        }
    }

    int ans = 0;
    for(int i = 1; i < n - 1; i++)
    ans = (ans + dp[n - 1][i] * ((pow2[i] - 1 + m) % m) % m) % m;  
    cout << ans << "\n";

}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	//IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

B. Complete The Graph

https://codeforces.ml/problemset/problem/715/B

题意

给定一个图，一些边的边权未知，现在让你给未知的边设边权(1<=w<=1e18)，满足s到t的最短路正好等于k

思路

将所有未知点的权值都设为k，然后跑dij求最短路,如果最短路比k还小就无解，如果没有未知点且最短路不等于k也无解。
然后遍历每一条未知边，将他的权值设为1，再跑最短路，如果最后距离小于k，那就将这条边的权值设为\(k - dis[t] + 1\),就找到答案结束即可，否则遍历下一条边做相同操作。
最后如果边权全为1后还不能找到一组解就是无解。

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
//#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e4 + 5;
const int M = 1e7 + 5;

int n, m, k, s, t;
int dis[N];
int vis[N], w[N];
vector<pair<int, int>>g[N];
pair<int, int>e[N];

inline void dij(int s){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    for(int i = 0; i < n; i++){
        dis[i] = k + 1;
        vis[i] = 0;
    }
    dis[s] = 0;
    q.push({dis[s], s});

    while(q.size()){
        auto [d, x] = q.top();
        q.pop();

        if(x == t) break;
        if(vis[x]) continue;
        vis[x] = 1;

        for(auto [to, id] : g[x]){
            if(dis[to] - dis[x] > w[id]){
                dis[to] = dis[x] + w[id];
                q.push({dis[to], to});
            }
        }

    }
}

inline int check(int id, int x){
    w[id] = x;
    dij(s);
    //cerr << dis[t] << "\n";
    return dis[t];
}

void solve() {
    cin >> n >> m >> k >> s >> t;

    vector<int>edge;
    for(int i = 1, u, v, d; i <= m; i++){
        cin >> u >> v >> d;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        e[i] = {u, v};
        w[i] = d;
        if(!d) {
            edge.push_back(i);
            w[i] = k;
        }
    }

    dij(s);
    //cerr << dis[t] << "\n";
    if(dis[t] < k) {
        cout << "NO\n";
        return;
    }

    if(dis[t] == k){
        cout << "YES\n";
        for(int i = 1; i <= m; i++)
            cout << e[i].first << " " << e[i].second << " " << w[i] << "\n";
        return;
    }
    else if(!edge.size()) {
        cout << "NO\n";
        return;
    }
    
    for(auto& id : edge){
        w[id] = 1;
        dij(s);
        if(dis[t] > k) continue;
        w[id] = k - dis[t] + 1;
        cout << "YES\n";
        for(int i = 1; i <= m; i++)
            cout << e[i].first << " " << e[i].second << " " << w[i] << "\n";
        return;
    }

    //cerr << f << "\n";
    cout << "NO\n";
    
}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

E. Flights

https://codeforces.ml/problemset/problem/241/E

题意

给定一个图，每条边只能设成1或2，要求1到n的路径的权值和一样，求构造方案。

思路

经典差分约束题
先去除1不能到的点和n不能到的点。
相当于\(1 \leq u - v \leq 2\) 转化成 \(u - v \leq 2\)且 \(v - u \leq -1\),然后给u到v建一条权值为2的边，v到u建一条权值为-1的边，跑bellman即可。

#include <bits/stdc++.h>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 5;
const int M = 1e6 + 5;

int n, m;
int c[N][2], vis[N], can[N], ans[N];
int dis[N];
vector<int>g[2][N];
vector<pair<int, int>>g2[N];
pair<int, int>e[N];

void dfs(int x, int k){
    c[x][k] = 1;
    for(auto to : g[k][x]){
        if(!c[to][k]) 
            dfs(to, k);
    }
}

bool bellman(){
    for(int i = 1; i <= n; i++)
        dis[i] = inf;

    dis[1] = 0;
    int f = 0;
    for(int j = 1; j <= n; j++) {
        f = 0;
        for(int i = 1; i <= n; i++){
            if(dis[i] == inf) continue;
            for(auto [to, w] : g2[i]) {
                if(dis[to] > dis[i] + w) {
                    dis[to] = dis[i] + w;
                    f = 1;
                }
            }
        }
        if(!f) break;
    }
    return f == 0;
}

void solve() {
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        g[0][u].push_back(v);
        g[1][v].push_back(u);
        e[i] = {u, v};
    }

    dfs(1, 0);
    dfs(n, 1);
    for(int i = 1; i <= n; i++){
        if(c[i][0] && c[i][1])
            can[i] = 1;
    }

    for(int i = 1; i <= m; i++){
        int u = e[i].first;
        int v = e[i].second;
        if(can[u] && can[v]) {
            g2[u].push_back({v, 2});
            g2[v].push_back({u, -1});
        }
    }

    if(!bellman()) {
        cout << "No" << '\n';
        return;
    }

    cout << "Yes\n";
    for(int i = 1; i <= m; i++){
        int u = e[i].first;
        int v = e[i].second;
        if(!can[u] || !can[v]) ans[i] = 1;
        else ans[i] = abs(dis[u] - dis[v]);
    }

    for(int i = 1; i <= m; i++)
        cout << ans[i] << '\n';

}

signed main()
{
    //freopen("kotlin.in", "r", stdin);
    //freopen("kotlin.out", "w", stdout);
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}

标签：图论,const,int,ll,dis,寒假,2023,include,define
From： https://www.cnblogs.com/yaqu-qxyq/p/17053187.html

k.Killer Sajin's Matrix

题意

思路

E. Anya's Simultaneous Exhibition

题意

思路

J. Perfect Matching

题意

思路

E - GCD of Path Weights

题意

思路

G - Farthest City

题意

思路

B. Complete The Graph

题意

思路

E. Flights

题意

思路

相关文章

赞助商

阅读排行

2023寒假 图论练习

k.Killer Sajin's Matrix

题意

思路

E. Anya's Simultaneous Exhibition

题意

思路

J. Perfect Matching

题意

思路

E - GCD of Path Weights

题意

思路

G - Farthest City

题意

思路

B. Complete The Graph

题意

思路

E. Flights

题意

思路

相关文章

赞助商

阅读排行

2023寒假图论练习