Submission #43895924

---

Source Code Expand

// LUOGU_RID: 117034367
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 1e5 + 10;
int n, d, x[N], y[N];
vector <int> v[N];
struct edge {
    int to, flow;
    unsigned pos;
};
vector <edge> a[N];
void add(int x, int y, int flow) {
    a[x].push_back((edge) { y, flow, (unsigned) a[y].size() });
    a[y].push_back((edge) { x, 0, (unsigned) a[x].size() - 1 });
}
int dep[N];
unsigned cur[N];
queue <int> q;
bool bfs(int s, int t) {
    F(i, s, t) dep[i] = 0;
    dep[s] = 1;
    q.push(s);
    while (q.size()) {
        int x = q.front(); q.pop();
        for (edge i: a[x])
            if (i.flow && !dep[i.to]) {
                dep[i.to] = dep[x] + 1;
                q.push(i.to);
            }
    }
    return dep[t];
}
int dfs(int x, int tt, int lim) {
    if (x == tt) return lim;
    int ans = 0, t;
    for (unsigned &i = cur[x]; i < a[x].size(); ++i)
        if (a[x][i].flow && dep[a[x][i].to] == dep[x] + 1 && (t = dfs(a[x][i].to, tt, min(lim, a[x][i].flow)))) {
            a[x][i].flow -= t, a[a[x][i].to][a[x][i].pos].flow += t;
            lim -= t, ans += t;
            if (!lim) return ans;
        }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        F(i, s, t) cur[i] = 0;
        ans += dfs(s, t, 1e9);
    } return ans;
}
void zhk() {
	read(n), read(d);
	int s = 0, t = n * d + n + 1;
	F(i, s, t) a[i].clear();
	F(i, 1, n * d) {
		read(x[i]), read(y[i]);
		add(s, i, 1);
		add(i, n * d + x[i], 1e9);
		add(i, n * d + y[i], 1e9);
	}
	F(i, 1, n) add(n * d + i, t, d);
	if (dinic(s, t) < n * d) puts("No");
	else {
		add(s, 1, 1e9);
		dinic(s, t);
		F(i, 1, n * d)
			if (!dep[i]) {
				puts("No");
				return;
			}
		F(i, s, t) a[i].clear();
		F(i, 2, n * d) {
			add(i, t, 1);
			add(n * d + x[i], i, 1e9);
			add(n * d + y[i], i, 1e9);
		}
		F(i, 1, n) add(s, n * d + i, d);
		dinic(s, t);
		// F(i, 1, n) cout << dep[n * d + i] << " "; cout << endl;
		F(i, 1, n)
			if (!dep[n * d + i]) {
				puts("No");
				return;
			}
		puts("Yes");
	}
}
signed main() {
	int _ = 1;
	cin >> _;
	while (_--) zhk();
	return 0;
}

Submission Info

Judge Result