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; } };