QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107886 | #1825. The King's Guards | BalintR# | WA | 2ms | 3600kb | C++20 | 4.5kb | 2023-05-23 04:56:45 | 2023-05-23 04:56:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
const int MN = 305;
const int MV = MN*3;
namespace Flow {
struct Edge {
int node, rev, cap;
bool real;
};
vector<Edge> adjList[MV];
void addEdge(int a, int b, int c){
adjList[a].pb({b, SZ(adjList[b]), c, true});
adjList[b].pb({a, SZ(adjList[a])-1, 0, false});
}
void rmEdge(int a, int b){
adjList[a].pop_back();
adjList[b].pop_back();
}
void reset(){
FR(i, MV) for(Edge &e : adjList[i]) if(!e.real) adjList[e.node][e.rev].cap += e.cap, e.cap = 0;
}
int ancFlow[MV], ePar[MV];
int qu[MV], ql, qr;
int bfs(int s, int t){
ms(ePar, -1);
ePar[s] = -2;
ql = qr = 0;
qu[qr++] = s;
ancFlow[s] = INF;
while(ql < qr){
int n1 = qu[ql++];
//dbg(n1);
for(Edge e : adjList[n1]){
int n2 = e.node;
if(!e.cap || ePar[n2] != -1) continue;
ancFlow[n2] = min(ancFlow[n1], e.cap);
ePar[n2] = e.rev;
qu[qr++] = e.node;
}
}
if(ePar[t] == -1) return 0;
int f = ancFlow[t];
int n1 = t;
while(n1 != s){
Edge &e = adjList[n1][ePar[n1]];
adjList[e.node][e.rev].cap -= f;
e.cap += f;
n1 = e.node;
}
return f;
}
int getFlow(int s, int t){
//cerr << s << ' ' << t << endl;
int res = 0;
while(true){
int f = bfs(s, t);
//dbg(f);
res += f;
if(!f) break;
}
//dbg(res);
return res;
}
}
int n, m, g;
int dsu[MN];
pair<int, pii> allEdges[MN*MN];
vector<pair<int, pii>> edges;
bool inAns[MN];
int find(int a){
return dsu[a] < 0 ? a : dsu[a] = find(dsu[a]);
}
void kruskal(){
sort(allEdges, allEdges + m);
ms(dsu, -1);
FR(i, m){
auto [c, p] = allEdges[i];
auto [a, b] = p;
a = find(a), b = find(b);
if(a != b){
dsu[b] = a;
edges.pb(allEdges[i]);
}
}
}
bool check(){
ms(dsu, -1);
FR(i, SZ(edges)) if(inAns[i]){
auto [a, b] = edges[i].sn;
a = find(a), b = find(b);
if(a != b) dsu[b] = a;
}
int numRoot = 0;
FR(i, n) numRoot += dsu[i] < 0;
FR(i, n) Flow::addEdge(n+i, n+n+find(i), 1);
bool good = Flow::getFlow(MV-2, MV-1) == numRoot;
Flow::reset();
FR(i, n) Flow::rmEdge(n+i, n+n+find(i));
return good;
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> g;
FR(i, m){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
allEdges[i] = {c, {a, b}};
}
kruskal();
//cerr << "a" << endl;
FR(i, g){
int k; cin >> k;
FR(i, k){
int a; cin >> a; a--;
Flow::addEdge(i, n+a, 1);
}
}
FR(i, n) Flow::addEdge(MV-2, i, 1);
FR(i, n) Flow::addEdge(n+n+i, MV-1, 1);
FR(i, n) Flow::addEdge(n+i, n+n+i, 1);
if(Flow::getFlow(MV-2, MV-1) != g) return !printf("-1\n");
Flow::reset();
FR(i, n) Flow::rmEdge(n+i, n+n+i);
int ans = 0;
fill_n(inAns, SZ(edges), true);
FORR(i, SZ(edges)-1, 0){
inAns[i] = false;
if(!check()) inAns[i] = true, ans += edges[i].fs;
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
5 6 2 1 2 1 1 3 4 2 4 2 2 5 5 3 4 7 4 5 3 2 1 2 2 2 4
output:
8
result:
ok answer is '8'
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3600kb
input:
10 19 6 1 5 761 6 8 606 3 9 648 2 4 115 5 8 814 1 2 712 4 10 13 5 10 797 3 4 956 1 7 73 5 7 192 2 7 110 5 9 302 3 6 120 6 9 494 1 3 668 3 7 966 6 10 974 3 8 41 2 10 5 3 6 4 3 2 1 7 2 10 8 3 10 7 8 2 2 1
output:
-1
result:
wrong answer expected '429', found '-1'