読者です 読者をやめる 読者になる 読者になる

SRM617 Med

問題:PieOrDolphin
概要:n(<=50)人が初めそれぞれ0を持っていて、人2つのペアがm(<=1000)個来る.それぞれのペアに対し、片方には+1,もう片方には-1を加算する。最終的に値の絶対値の総和を最小化するような+1,-1の足し方を求めよ

解説:editorial参照

ミス:
edge e=G[i][j];
e.to=x;
みたいなことをしていたが、&eにしなきゃだめ

segmentation faultは範囲外アクセス,深すぎるdfsなど。
後者はloopが起こりうるときにvisitedなどで対策してない場合に起こる

単にザコ

my solution:

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define all(c) c.begin(),c.end()
using namespace std;
struct edge{int to,rev;bool use;};
int f[50];
vector<edge> G[50];
bool visited[50];
bool dfsm(int v,int p){
//	if(p==-1) cout << "dfsm  " << v << endl;
//	else cout << "m     " << v << " from " << p << endl;
	if(p==-1) rep(i,50) visited[i]=false;
	visited[v]=true;
	if(f[v]<=-1) return true;
	rep(i,G[v].size()){
		edge &e=G[v][i];
		if(visited[e.to] || e.use==1) continue;
		if(dfsm(e.to,v)){
//			cout << e.to << "de end" << endl;
			e.use=1;
			G[e.to][e.rev].use=0;
			f[e.to]+=2;
			f[v]-=2;
			return true;
		}
	}
	return false;
}
bool dfsp(int v,int p){
//	if(p==-1) cout << "dfsp  " << v << endl;
//	else cout << "p     " << v << " from " << p << endl;
	if(p==-1) rep(i,50) visited[i]=false;
	visited[v]=true;
	if(f[v]>=1) return true;
	rep(i,G[v].size()){
		edge &e=G[v][i];
		if(visited[e.to] || e.use==0) continue;
		if(dfsp(e.to,v)){
//			cout << e.to << "de end" << endl;
//			cout << e.to << " " << e.use << " " << G[e.to][e.rev].to << endl;
			e.use=false;
//			cout << v << " " << i << " become 0" << endl;
			G[e.to][e.rev].use=true;
//			cout << e.to << " " << e.rev << " become 1" << endl;
			f[e.to]-=2;
			f[v]+=2;
			return true;
		}
	}
	return false;
}
class PieOrDolphin{
	public:
	vector<int> Distribute(vector<int> c1,vector<int> c2){
		int eg[1000];
		vector<int> di;
		rep(i,c1.size()){
			G[c1[i]].push_back({c2[i],G[c2[i]].size(),1});
			G[c2[i]].push_back({c1[i],G[c1[i]].size()-1,0});
			f[c2[i]]++;
			eg[i]=G[c1[i]].size()-1;
			f[c1[i]]--;
		}
		while(true){
			bool update=false;
			rep(i,50){
				if(f[i]<-1) { dfsp(i,-1); update=true; break;}
				if(f[i]>1)  { dfsm(i,-1); update=true; break;}
			}
			if(!update) break;
		}
		rep(i,c1.size()){
			edge e=G[c1[i]][eg[i]];
			di.push_back((e.use ? 1 : 2));
//			cout << c1[i] << " " << eg[i] << " " << e.use << endl;
		}
//		rep(i,50) cout << f[i] << " ";
		return di;
	}
};