結果

問題 No.119 旅行のツアーの問題
ユーザー vjudge1
提出日時 2024-12-21 18:54:40
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,502 bytes
コンパイル時間 1,486 ms
コンパイル使用メモリ 161,356 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 18:54:43
合計ジャッジ時間 2,470 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
struct Edge{
    int v,nxt;
    int c;
};
#define MAXN 85
#define MAXM 10005
int n,m;
int x,y;
int s;
Edge e[MAXM*2]; int h[MAXN],ec;
int cur[MAXN],dis[MAXN];
int qu[MAXN],fr,bk;
int en;
void adde(int u,int v,int c){
    e[ec].v=v,e[ec].nxt=h[u],e[ec].c=c;
    h[u]=ec; ++ec;
    return;
}
void addp(int u,int v,int c){
    // std::cout<<u<<' '<<v<<' '<<c<<'\n';
    adde(u,v,c),adde(v,u,0);
    return;
}
bool bfs(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    
    qu[fr=bk=1]=s; dis[1]=0;
    while(fr<=bk){
        int u=qu[fr++];
        for(int i=h[u];i+1;i=e[i].nxt){
            int v=e[i].v;
            if(!e[i].c) continue;
            if(dis[u]+1<dis[v]) qu[++bk]=v,dis[v]=dis[u]+1;
        }
    }
    return dis[t]!=0x3f3f3f3f;
}
int dfs(int u,int t,int f){
    if(u==t) return f;
    int cnt=0;
    for(;cur[u]+1;cur[u]=e[cur[u]].nxt){
        int v=e[cur[u]].v; int c=e[cur[u]].c;
        if(dis[u]+1!=dis[v]||(!c)) continue;
        int now=dfs(v,t,std::min(f,c));
        f-=now,cnt+=now; e[cur[u]].c-=now,e[cur[u]^1].c+=now;
        if(!f) break;
    }
    return cnt;
}
int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)){
        for(int i=1;i<=en;i++) cur[i]=h[i];
        res+=dfs(s,t,0x3f3f3f3f);
    }
    return res;
}
int main(){
    std::ios::sync_with_stdio(false);
    
    memset(h,-1,sizeof(h));
    
    std::cin>>n; en=2*n+2;
    for(int i=1;i<=n;i++){
        std::cin>>x>>y;
        addp(1,2*i,x),addp(2*i+1,2*n+2,y);
        s+=(x+y);
        addp(2*i,2*i+1,0x3f3f3f3f);
    }
    std::cin>>m;
    for(int i=1;i<=m;i++){
        std::cin>>x>>y; ++x,++y;
        addp(2*x,2*y+1,0x3f3f3f3f);
    }
    std::cout<<s-dinic(1,2*n+2)<<'\n';
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0