結果
問題 |
No.2320 Game World for PvP
|
ユーザー |
|
提出日時 | 2023-05-26 23:19:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,072 bytes |
コンパイル時間 | 1,948 ms |
コンパイル使用メモリ | 172,344 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 10:49:30 |
合計ジャッジ時間 | 3,209 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 WA * 8 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=200; const long long inf=1e17; struct node{ int u,to; long long w; }edge[N*N]; int head[N],arrange[N],cur[N],a[N],b[N],p[N],c[N][N]; int n,m,s,t,x,y,z,k,sx,tx; void add(int x,int y,long long z) { edge[k].u=y; edge[k].to=head[x]; edge[k].w=z; head[x]=k++; edge[k].u=x; edge[k].to=head[y]; edge[k].w=0; head[y]=k++; } bool bfs(){ memset(arrange,0,sizeof(arrange)); queue<int>q; q.push(s); arrange[s]=1; while (!q.empty()){ int v=q.front(); q.pop(); if (t==v) return 1; for (int i=head[v];i!=-1;i=edge[i].to){ int u=edge[i].u; if (arrange[u]||!edge[i].w) continue; arrange[u]=arrange[v]+1; q.push(u); } } return 0; } long long dfs(int now,long long maxlow,int t){ if (now==t) return maxlow; long long ret=0; for (int &i=cur[now];i!=-1;i=edge[i].to){ int u=edge[i].u; if (arrange[u]!=arrange[now]+1||!edge[i].w) continue; long long f=dfs(u,min(maxlow-ret,edge[i].w),t); edge[i].w-=f; edge[i^1].w+=f; ret+=f; if (f==maxlow) return maxlow; } return ret; } long long dinic(){ long long ans=0; while (bfs()){ memcpy(cur,head,sizeof(head)); ans+=dfs(s,inf,t); } return ans; } int main(){ scanf("%d%d%d",&n,&sx,&tx); memset(head,-1,sizeof(head));k=0; for (int i=1;i<=sx;i++){ scanf("%d",&a[i]); p[a[i]]=1; } for (int i=1;i<=tx;i++){ scanf("%d",&b[i]); p[b[i]]=1; } long long ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&c[i][j]); for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) if (!p[i]||!p[j]) ans+=c[i][j]; for (int i=1;i<=sx;i++) for (int j=i+1;j<=sx;j++) ans+=c[a[i]][a[j]]; for (int i=1;i<=tx;i++) for (int j=i+1;j<=tx;j++) ans+=c[b[i]][b[j]]; s=n*2+1; t=n*2+2; int cnt=0; for (int i=1;i<=n;i++) if (!p[i]){ long long w=0; for (int j=1;j<=sx;j++) w+=c[i][a[j]]; add(s,i*2-1,w); w=0; for (int j=1;j<=tx;j++) w+=c[i][b[j]]; add(i*2,t,w); add(i*2-1,i*2,inf); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (!p[i]&&!p[j]&&i!=j) add(i*2-1,j*2,c[i][j]); printf("%lld\n",ans-dinic()); }