| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 64648 | jangwonyoung | Arranging Tickets (JOI17_arranging_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
int n,m,s,t;
int a[100001];
int b[100001];
ll c[100001];
ll eq[200001];
ll d[200003],d2[200003];
bool vis[200003],inq[200003];
ll cp[1000001],wt[1000001];
vector<pair<int,int> >adj[200003];
int sz;
bool fuck[100001];
int q[3][200003];
int st[3],en[3];
void init(){
for(int i=1; i<=t ;i++){
adj[i].clear();
d[i]=d2[i]=0;
}
sz=0;
}
void addedge(int u,int v,ll cap,ll wei){
cp[sz]=cap;cp[sz^1]=0;
wt[sz]=wei;wt[sz^1]=-wei;
adj[u].pb({v,sz});
adj[v].pb({u,sz^1});
sz+=2;
}
ll dfs(int id,ll f){
if(id==t) return f;
if(vis[id]) return 0;
vis[id]=true;
ll res=0;
for(auto cur:adj[id]){
if(d[cur.fi]==d[id]+wt[cur.se] && cp[cur.se]>0){
ll tmp=dfs(cur.fi,min(f,cp[cur.se]));
if(tmp){
cp[cur.se]-=tmp;
cp[cur.se^1]+=tmp;
return tmp;
}
}
}
return 0;
}
void sp(){
for(int i=1; i<=t ;i++){
d2[i]+=d[i];
d[i]=1e18;
inq[i]=false;
}
st[0]=st[1]=st[2]=en[0]=1;
en[1]=en[2]=0;
q[0][1]=s;
d[s]=0;
for(int j=0; j<=2 ;j++){
while(st[j]<=en[j]){
int cur=q[j][st[j]];
st[j]++;
if(d[cur]<j) continue;
if(inq[cur]) return -31239;
inq[cur]=true;
for(auto newi:adj[cur]){
if(d[newi.fi]>d[cur]+wt[newi.se]+d2[cur]-d2[newi.fi] && cp[newi.se]>0){
d[newi.fi]=d[cur]+wt[newi.se]+d2[cur]-d2[newi.fi];
if(d[newi.fi]<=2){
en[d[newi.fi]]++;
q[d[newi.fi]][en[d[newi.fi]]]=newi.fi;
}
}
}
}
}
}
ll flow(){
ll res=0;//min cost
while(true){
sp();
if(d[t]==1e18) return res;
while(true){
for(int j=1; j<=t ;j++) vis[j]=false;
ll tmp=dfs(s,1e18);
if(tmp==0) break;
res+=tmp*(d[t]+d2[t]);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
s=n+1,t=n+2;
for(int i=1; i<=m ;i++){
cin >> a[i] >> b[i] >> c[i];
if(a[i]==b[i]){
fuck[i]=true;
continue;
}
if(a[i]>b[i]) swap(a[i],b[i]);
b[i]--;
if(a[i]==1){
eq[n]-=c[i];
eq[b[i]]+=c[i];
}
else{
eq[a[i]-1]+=c[i];
eq[b[i]]-=c[i];
}
}
ll ans=1e18;
for(int i=0; i<2 ;i++){
init();
bool odd=i;
for(int j=1; j<=n ;j++){
ll cur=eq[j]-odd;
odd=false;
if(cur&1){
cur++;
odd=true;
}
if(cur>0) addedge(s,j,cur/2,0);
else addedge(j,t,-cur/2,0);
if(j==1) addedge(1,n,1e18,2);
else addedge(j,j-1,1e18,0);
}
for(int j=1; j<=m ;j++){
if(fuck[j]) continue;
if(a[j]==1) addedge(b[j],n,c[j],1);
else addedge(a[j]-1,b[j],c[j],1);
}
ans=min(ans,flow()+i);
}
cout << ans << endl;
}