結果

問題 No.1582 Vertexes vs Edges
ユーザー むかでむかで
提出日時 2021-07-02 23:14:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 5,456 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 219,196 KB
実行使用メモリ 21,944 KB
最終ジャッジ日時 2024-06-29 13:02:27
合計ジャッジ時間 5,878 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 60 ms
19,052 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 10 ms
5,632 KB
testcase_08 AC 29 ms
10,976 KB
testcase_09 AC 57 ms
17,988 KB
testcase_10 AC 35 ms
12,588 KB
testcase_11 AC 6 ms
5,376 KB
testcase_12 AC 25 ms
9,664 KB
testcase_13 AC 64 ms
13,644 KB
testcase_14 AC 62 ms
13,856 KB
testcase_15 AC 94 ms
17,608 KB
testcase_16 AC 40 ms
10,388 KB
testcase_17 AC 61 ms
13,364 KB
testcase_18 AC 113 ms
20,876 KB
testcase_19 AC 51 ms
14,072 KB
testcase_20 AC 53 ms
12,688 KB
testcase_21 AC 48 ms
11,808 KB
testcase_22 AC 86 ms
18,872 KB
testcase_23 AC 31 ms
8,836 KB
testcase_24 AC 17 ms
5,888 KB
testcase_25 AC 47 ms
11,560 KB
testcase_26 AC 38 ms
9,844 KB
testcase_27 AC 90 ms
17,500 KB
testcase_28 AC 27 ms
7,736 KB
testcase_29 AC 71 ms
15,272 KB
testcase_30 AC 46 ms
10,804 KB
testcase_31 AC 77 ms
16,244 KB
testcase_32 AC 30 ms
8,684 KB
testcase_33 AC 119 ms
21,816 KB
testcase_34 AC 126 ms
21,840 KB
testcase_35 AC 132 ms
21,944 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

template<class T>
vector<T> make_vec(size_t a){
	return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
	return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//-------------------------------------------------
//--Dinic
//-------------------------------------------------
template<typename F>
class Dinic
{
private:
    struct Edge {int to; F cap; int rev;};
    struct EdgeLocation {int from,idx;};
    using FlowGraph = vector<vector<Edge> >;
    const F F_INF;
    FlowGraph G;
    vector<int> level, iter;
    int idx;
    vector<EdgeLocation> eloc;
    bool leveling(int s, int t){
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> que;
        que.emplace(s);
        while(!que.empty()){
            int v = que.front(); que.pop();
            for(Edge &e:G[v]){
                if (level[e.to]<0 && e.cap>0){
                    level[e.to] = level[v]+1;
                    que.emplace(e.to);
                }
            }
        }
        return level[t]>=0;
    }
    F dfs(int v, int t, F flow){
        if (v==t) return flow;
        for(int &i=iter[v]; i<G[v].size(); i++){
            Edge &e = G[v][i];
            if (level[v]<level[e.to] && e.cap>0){
                F res = dfs(e.to,t,min(flow,e.cap));
                if (res>0){
                    e.cap-=res;
                    G[e.to][e.rev].cap+=res;
                    return res;
                }
            }
        }
        return 0;
    }
public:
    Dinic(int N):G(N),level(N),iter(N),idx(0),F_INF(numeric_limits<F>::max()){}
    int add_edge(int from, int to, F cap){
        G[from].push_back({to,cap,(int)G[to].size()});
        int fidx = G[from].size()-1;
        G[to].push_back({from,0,fidx});
        eloc.push_back({from,fidx});
        return idx++;
    }
    F max_flow(int s, int t){
        F ret=0;
        while(leveling(s,t)){
            fill(iter.begin(), iter.end(), 0);
            for(F flow; (flow=dfs(s,t,F_INF))>0;)
                ret+=flow;
        }
        return ret;
    }
    F max_flow(int s, int t, F flow_limit){
        F ret=0;
        while(leveling(s,t)){
            fill(iter.begin(), iter.end(), 0);
            for(F flow; flow_limit>0 && (flow=dfs(s,t,flow_limit))>0;){
                ret+=flow;
                flow_limit-=flow;
            }
        }
        return ret;
    }
    F get_flow(int ei){
        assert(ei<idx);
        const Edge &e = G[eloc[ei].from][eloc[ei].idx];
        return G[e.to][e.rev].cap;
    }
    F get_cap(int ei){
        assert(ei<idx);
        const Edge &e = G[eloc[ei].from][eloc[ei].idx];
        return e.cap+G[e.to][e.rev].cap;
    }
    void change_edge(int ei, F cap, F flow){
        assert(ei<idx && flow<=cap);
        Edge &e = G[eloc[ei].from][eloc[ei].idx];
        e.cap = cap-flow;
        G[e.to][e.rev].cap = flow;
    }
    vector<bool> min_cut(int s){
        vector<bool> ret(G.size());
        ret[s] = true;
        queue<int> que;
        que.emplace(s);
        while(!que.empty()){
            int v = que.front(); que.pop();
            for(Edge &e:G[v]){
                if (!ret[e.to] && e.cap>0){
                    ret[e.to] = true;
                    que.emplace(e.to);
                }
            }
        }
        return ret;
    }
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin>>N;

    vector<vi> G(N);
    vi X(N-1),Y(N-1);
    rep(i,N-1){
        int u,v; cin>>u>>v; u--; v--;
        G[u].pb(v);
        G[v].pb(u);
        X[i]=u, Y[i]=v;
    }

    vi color(N,-1);
    auto dfs = [&](auto &dfs, int v, int p=-1, int c=0)->void{
        color[v] = c;
        for(auto u:G[v]){
            if (u==p) continue;
            dfs(dfs,u,v,1-c);
        }
    };

    dfs(dfs,0);
    Dinic<int> dinic(N+2);
    const int source=N, sink=N+1;
    rep(i,N){
        if (color[i]==0) dinic.add_edge(source,i,1);
        else dinic.add_edge(i,sink,1);
    }
    rep(i,N-1){
        if (color[X[i]]==0) dinic.add_edge(X[i],Y[i],1);
        else dinic.add_edge(Y[i],X[i],1);
    }

    cout<<dinic.max_flow(source,sink)<<"\n";
    return 0;
}
0