QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353291#1825. The King's GuardsLaStataleBlueWA 0ms3616kbC++234.5kb2024-03-14 01:34:542024-03-14 01:34:55

Judging History

你现在查看的是最新测评结果

  • [2024-03-14 01:34:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-03-14 01:34:54]
  • 提交

answer

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

using pi = pair<int,int>;
#define sz(x) int((x).size())
template<class F> struct Dinic {
    struct Edge { int to, rev; F cap; };
    int N; vector<vector<Edge>> adj;
    void init(int _N) { N = _N; adj.resize(N); } //0-based
    pi ae(int a, int b, F cap, F rcap = 0) {
        assert(min(cap,rcap) >= 0); // saved me > once
        adj[a].push_back({b,sz(adj[b]),cap});
        adj[b].push_back({a,sz(adj[a])-1,rcap});
        return {a,sz(adj[a])-1};
    }
    F edgeFlow(pi loc) { // get flow along original edge
        const Edge& e = adj.at(loc.first).at(loc.second);
        return adj.at(e.to).at(e.rev).cap;
    }
    vector<int> lev, ptr;
    bool bfs(int s,int t){//level=shortest dist from source
        lev = ptr = vector<int>(N);
        lev[s] = 1; queue<int> q({s});
        while (sz(q)) { int u = q.front(); q.pop();
            for(auto& e: adj[u]) if (e.cap && !lev[e.to]) {
                q.push(e.to), lev[e.to] = lev[u]+1;
                if (e.to == t) return 1;
            }
        }
        return 0;
    }
    F dfs(int v, int t, F flo) {
        if (v == t) return flo;
        for (int& i = ptr[v]; i < sz(adj[v]); i++) {
            Edge& e = adj[v][i];
            if (lev[e.to]!=lev[v]+1||!e.cap) continue;
            if (F df = dfs(e.to,t,min(flo,e.cap))) {
                e.cap -= df; adj[e.to][e.rev].cap += df;
                return df; } // saturated $\geq1$ one edge
        }
        return 0;
    }
    F maxFlow(int s, int t) {
        F tot = 0; while (bfs(s,t)) while (F df =
            dfs(s,t,numeric_limits<F>::max())) tot += df;
        return tot;
    }
};

struct RollbackUF {
    vector<int> e; vector<pair<int,int>> st;
    RollbackUF(int n) : e(n, -1) {}
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : find(e[x]); }
    int time() { return st.size(); }
    void rollback(int t) {
        for(int i=time();i-->t;) e[st[i].first] = st[i].second;
        st.resize(t);
    }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        st.push_back({a, e[a]}); st.push_back({b, e[b]});
        e[a] += e[b]; e[b] = a; return true;
    }
};

void solve([[maybe_unused]] int t){
    int n,r,g;
    cin>>n>>r>>g;
    
    vector<array<int,3>> ed;
    for(int i=0;i<r;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        ed.push_back({c,a,b});
    }
    sort(ed.begin(),ed.end());
    
    vector opz(g,vector<int>());
    for(int i=0;i<g;i++){
        int k;
        cin>>k;
        opz[i].resize(k);
        for(auto &j : opz[i]){
            cin>>j;
            j--;
        }
    }
    
    RollbackUF ds(n);
    vector<bool> req(n,false);
   
    auto calc = [&](){
        Dinic<int> mf;
        int source = g+n, sink = n+g+1;
        mf.init(n+g+2);
        
        for(int i=0;i<g;i++){
            for(auto x : opz[i]){
                mf.ae(i,g+ds.find(x),1);
            }
        }
        
        for(int i=0;i<g;i++)mf.ae(source,i,1);
        for(int i=0;i<n;i++)mf.ae(g+i,sink,1);
        
        if(mf.maxFlow(source,sink)!=g){
            cout<<"-1\n";
            exit(0);
        }
        
        vector vis(n+g,false);
        
        auto dfs = [&](auto &dfs,int nodo)->void{
            if(vis[nodo])return;
            vis[nodo]=true;
            
            for(auto [to,rev,cap] : mf.adj[nodo]){
                if(to!=sink && to!=source && cap==0)dfs(dfs,to);
            }
        };
        
        for(int i=0;i<n;i++){
            bool ok=true;
            for(auto [to,rev,cap] : mf.adj[g+i]){
                if(to!=sink && cap==1)ok=false;
            }
            
            if(ok)dfs(dfs,g+i);
        }
        
        for(int i=0;i<n;i++){
            if(vis[g+i]==false)req[i]=true;
            else req[i]=false;
        }
    };
    
    calc();
    
    int ans=0,comp=n;
    for(auto [cost,x,y] : ed){
        if(!req[ds.find(x)] || !req[ds.find(y)]){
            if(ds.join(x,y)){
                ans+=cost;
                calc();
            }
        }
    }
    if(comp!=g){
        cout<<"-1\n";
        return;
    }
    cout<<ans<<"\n";
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

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:

-1

result:

wrong answer expected '8', found '-1'