結果

問題 No.1582 Vertexes vs Edges
ユーザー むかで
提出日時 2021-07-02 23:14:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 5,456 bytes
コンパイル時間 2,912 ms
コンパイル使用メモリ 212,408 KB
最終ジャッジ日時 2025-01-22 16:52:49
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0