讨论详情 - 岱陌存理

思路解析
图论题
YIZHIYANG 一只羊 LV 10 SU @ 2026-3-29 8:59:42

P1341 无序字母对

// Problem: P1341 无序字母对
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1341
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// by 1zhio2
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int g[200][200];
int d[200];
int n;
char s[10];
vector<int> p;

void dfs(int u) {
    for (int v = 0; v < 200; v++) {
        if (g[u][v]) {
            g[u][v] = g[v][u] = 0;
            dfs(v);
        }
    }
    p.push_back(u);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    int mi = 200;
    for (int i = 0; i < n; i++) {
        cin >> s;
        int u = s[0], v = s[1];
        g[u][v] = g[v][u] = 1;
        d[u]++;
        d[v]++;
        mi = min({mi, u, v});
    }

    int c = 0;
    int st = -1;
    for (int i = 0; i < 200; i++) {
        if (d[i] % 2 == 1) {
            c++;
            if (st == -1) st = i;
        }
    }

    if (st == -1) st = mi;

    if (c != 0 && c != 2) {
        cout << "No Solution" << endl;
        return 0;
    }

    dfs(st);

    if (p.size() != n + 1) {
        cout << "No Solution" << endl;
    } else {
        for (int i = n; i >= 0; i--) {
            cout << (char)p[i];
        }
        cout << endl;
    }

    return 0;
}

P3398 仓鼠找 sugar

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int S = 100005;
const int M = 200005;

int hd[S], to[M], nx[M], tot;
int dep[S], up[S][20];

void add(int u, int v) {
    to[++tot] = v;
    nx[tot] = hd[u];
    hd[u] = tot;
}

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    up[u][0] = p;
    for (int i = 1; i <= 17; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int i = hd[u]; i; i = nx[i]) {
        int v = to[i];
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        int t = u; u = v; v = t;
    }
    for (int i = 17; i >= 0; --i) {
        if (dep[up[u][i]] >= dep[v]) {
            u = up[u][i];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 17; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int x = lca(a, b);
        int y = lca(c, d);
        if (dep[x] < dep[y]) {
            int t = x; x = y; y = t;
            t = a; a = c; c = t;
            t = b; b = d; d = t;
        }
        if (lca(x, c) == x || lca(x, d) == x) {
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
    }
    return 0;
}

P4667 [BalticOI 2011] Switch the Lamp On (Day1)

// Problem: P4667 [BalticOI 2011] Switch the Lamp On (Day1)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4667
// Memory Limit: 125 MB
// Time Limit: 150 ms
// by 1zhio2
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
char c[505][505];
int d[505][505];

int dx[4] = {-1, -1, 1, 1};
int dy[4] = {-1, 1, -1, 1};
int ex[4] = {-1, -1, 0, 0};
int ey[4] = {-1, 0, -1, 0};
char cd[4] = {'\\', '/', '/', '\\'};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
        }
    }
    if ((n + m) % 2 == 1) {
        cout << "NO SOLUTION\n";
        return 0;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            d[i][j] = 1000000000;
        }
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    d[0][0] = 0;
    while (!q.empty()) {
        auto p = q.front();
        q.pop_front();
        int x = p.first;
        int y = p.second;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
                int cx = x + ex[i];
                int cy = y + ey[i];
                int w = (c[cx][cy] != cd[i]);
                if (d[x][y] + w < d[nx][ny]) {
                    d[nx][ny] = d[x][y] + w;
                    if (w == 0) {
                        q.push_front({nx, ny});//队首
                    } else {
                        q.push_back({nx, ny});
                    }
                }
            }
        }
    }
    cout << d[n][m] << "\n";
    return 0;
}

二分图

// Problem: P3386 【模板】二分图最大匹配
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3386
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// by 1zhio2
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 505;
int n ,m ,e;
int p[N],v[N];
vector<int> g[N];

bool dfs(int u ,int t){
	for(int x :g[u]){
		if(v[x] == t) continue;
		v[x] = t;
		if(!p[x] || dfs(p[x],t)){ //???
			p[x] = u;
			return 1;
		}
	}
	return 0;
}


int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,m,e;
    cin>>n>>m>>e;
    for(int i = 0;i<e;++i){
    	int u,v;
    	cin>>u>>v;
    	g[u].push_back(v);
    }
    
    int ans = 0;
    
    for(int i =1;i<=n;++i){
    	if(dfs(i,i)){
    		ans++;
    	}
    }
    cout<<ans<<endl;
    return 0;
}

Dinic

// Problem: P3386 【模板】二分图最大匹配
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3386
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// by 1zhio2
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1005;
const int M = 2e5 + 5;
const int inf = 1e9;

int n, m, e, s, t;
int h[N], cur[N], d[N], c = 1;

struct E {
    int v, n, f;
} a[M];

void add(int u, int v, int f) {
    a[++c] = {v, h[u], f}; h[u] = c;
    a[++c] = {u, h[v], 0}; h[v] = c;
}

bool bfs() {
    memset(d, -1, sizeof d);
    copy(h, h + N, cur);
    queue<int> q;
    q.push(s); d[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; i; i = a[i].n) {
            int v = a[i].v;
            if (a[i].f && d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return d[t] != -1;
}

int dfs(int u, int l) {
    if (u == t || !l) return l;
    int r = 0;
    for (int &i = cur[u]; i; i = a[i].n) {
        int v = a[i].v;
        if (d[v] == d[u] + 1 && a[i].f) {
            int f = dfs(v, min(l - r, a[i].f));
            if (!f) continue;
            a[i].f -= f; a[i ^ 1].f += f;
            r += f;
            if (r == l) break;
        }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> e;
    s = 0; t = n + m + 1;
    for (int i = 1; i <= n; i++) add(s, i, 1);
    for (int i = 1; i <= m; i++) add(i + n, t, 1);
    for (int i = 0; i < e; i++) {
        int u, v; cin >> u >> v;
        if (u <= n && v <= m) add(u, v + n, 1);
    }
    int ans = 0;
    while (bfs()) ans += dfs(s, inf);
    cout << ans << endl;
    return 0;
}

目前还没有评论...

图论题

P1341 无序字母对

P3398 仓鼠找 sugar

P4667 [BalticOI 2011] Switch the Lamp On (Day1)

二分图

Dinic

0 条评论

还没有账户？

登录