제출 #64653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64653		jangwonyoung	Arranging Tickets (JOI17_arranging_tickets)	C++14	65 / 100	6062 ms	48040 KiB

arranging_tickets

#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]+d2[id]-d2[cur.fi] && 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;
				f-=tmp;
				res+=tmp;
			}
			if(f==0) return res;
		}
	}
	//if(res!=0) vis[id]=false;
	return res;
}
void sp(){
	for(int i=1; i<=t ;i++){
		d2[i]+=d[i];
		d[i]=1e18;
	}
	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;
			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;
		for(int j=1; j<=t ;j++) vis[j]=false;
		ll tmp=dfs(s,1e18);
		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;
}

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15