Submission #64643

#	Time	Username	Problem	Language	Result	Execution time	Memory
64643		jangwonyoung	Arranging Tickets (JOI17_arranging_tickets)	C++14	65 / 100	286 ms	40288 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];
bool vis[200003],inq[200003];
ll cp[1000001],wt[1000001];
vector<pair<int,int> >adj[200003];
int sz;
bool fuck[100001];
void init(){
	for(int i=1; i<=t ;i++) adj[i].clear();
	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;
}
ll flow(){
	if(n>3000) return 0;
	ll res=0;//min cost 
	while(true){
		for(int i=1; i<=t ;i++){
			d[i]=1e18;
			inq[i]=false;
		}
		queue<int>q;
		d[s]=0;
		inq[s]=true;
		q.push(s);
		while(!q.empty()){
			int cur=q.front();
			q.pop();
			inq[cur]=false;
			for(auto newi:adj[cur]){
				if(d[newi.fi]>d[cur]+wt[newi.se] && cp[newi.se]>0){
					d[newi.fi]=d[cur]+wt[newi.se];
					if(!inq[newi.fi]){
						inq[newi.fi]=true;
						q.push(newi.fi);
					}
				}
			}
		}
		if(d[t]==1e18) return res;
		if(d[t]>2) while(true);
		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];
		}
	}
}
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