PKU 3422, 2762
久しぶりにPOJ Monthlyでもやってみようと思ってやることにしました。
3422: Kaka's Matrix Travels
いつしかこのブログに書いたはずのDiv1Hardとほとんど同じ問題です。まったく同じ最小費用流をすれば解けます。
#include <vector> #include <algorithm> #include <iostream> #include <queue> #include <cstdio> using namespace std; typedef int Weight; const Weight INF=99999999; struct Edge{ int dst,cap;Weight cost,rev; }; typedef vector<Edge> Node; typedef vector<Node> Graph; //srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){ G[src].push_back((Edge){dst,cap,cost,G[dst].size()}); G[dst].push_back((Edge){src,0,-cost,G[src].size()-1}); } //sからtへの流量fの最小費用流を求める //流せない場合は-1を返す int min_cost_flow(Graph &G,int s,int t,int f){ typedef pair<int,int> P; int res=0; int V=G.size(); vector<Weight> h(V,0); vector<int> prevv(V); vector<int> preve(V); while(f>0){ priority_queue<P,vector<P>,greater<P> > que; vector<Weight> dist(V,INF); dist[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(dist[v]<p.first)continue; for(int i=0;i<(int)G[v].size();i++){ Edge &e=G[v][i]; if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){ dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst]; prevv[e.dst]=v; preve[e.dst]=i; que.push(P(dist[e.dst],e.dst)); } } } if(dist[t]==INF){ return -1; } for(int v=0;v<V;v++)h[v]+=dist[v]; int d=f; for(int v=t;v!=s;v=prevv[v]){ d=min(d,G[prevv[v]][preve[v]].cap); } f-=d; res+=d*h[t]; for(int v=t;v!=s;v=prevv[v]){ Edge &e=G[prevv[v]][preve[v]]; e.cap-=d; G[v][e.rev].cap+=d; } } return res; } int c[100][100]; int main(){ int a,b; scanf("%d%d",&a,&b); Graph g=Graph(2*a*a+2); int S=2*a*a; int T=2*a*a+1; for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ scanf("%d",&c[i][j]); add_edge(g,i*a+j,i*a+j+a*a,1,1000-c[i][j]); add_edge(g,i*a+j,i*a+j+a*a,9999,1000); } } add_edge(g,S,0,99999,0); add_edge(g,2*a*a-1,T,99999,0); for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i<a-1)add_edge(g,i*a+j+a*a,(i+1)*a+j,9999,0); if(j<a-1)add_edge(g,i*a+j+a*a,i*a+j+1,9999,0); } } printf("%d\n",1000*(2*a-1)*b-min_cost_flow(g,S,T,b)); }
2762: Going from u to v or from v to u?
高2のPKUガチ勢していたときは解けなかった問題。n<1000,m<6000なのにO(n+m)でも結構時間を使います(vector使ったら1秒以上かかりそう)
強連結成分分解をして、できたグラフが直線グラフになっていればYesです。
#include<stdio.h> #include<algorithm> using namespace std; int next[10000]; int first[2000]; int to[10000]; int next2[10000]; int first2[2000]; int to2[10000]; int num[2000]; int rev[2000]; int sccnum[2000]; int in[2000]; int out[2000]; int now; void dfs1(int a){ num[a]=now; for(int i=first[a];~i;i=next[i]){ if(!~num[to[i]])dfs1(to[i]); } rev[now++]=a; } void dfs2(int a){ sccnum[a]=now; for(int i=first2[a];~i;i=next2[i]){ if(!~sccnum[to2[i]])dfs2(to2[i]); } } int main(){ int T; scanf("%d",&T); while(T--){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)first[i]=first2[i]=num[i]=rev[i]=sccnum[i]=-1; for(int i=0;i<a;i++)in[i]=out[i]=-1; for(int i=0;i<b;i++)next[i]=next2[i]=-1; for(int i=0;i<b;i++){ int c,d; scanf("%d%d",&c,&d); c--;d--; next[i]=first[c]; first[c]=i; to[i]=d; next2[i]=first2[d]; first2[d]=i; to2[i]=c; } now=0; for(int i=0;i<a;i++){ if(!~num[i])dfs1(i); } now=0; for(int i=a-1;i>=0;i--){ if(!~sccnum[rev[i]]){ dfs2(rev[i]); now++; } } // for(int i=0;i<a;i++)printf("%d\n",sccnum[i]); bool ok=true; for(int i=0;i<a;i++){ for(int j=first[i];~j;j=next[j]){ if(sccnum[i]==sccnum[to[j]])continue; if(~in[sccnum[to[j]]]&&in[sccnum[to[j]]]!=sccnum[i])ok=false; if(!~in[sccnum[to[j]]])in[sccnum[to[j]]]=sccnum[i]; if(~out[sccnum[i]]&&out[sccnum[i]]!=sccnum[to[j]])ok=false; if(!~out[sccnum[i]])out[sccnum[i]]=sccnum[to[j]]; } } int noin=0; int noout=0; for(int i=0;i<now;i++){ if(!~in[i])noin++; if(!~out[i])noout++; } if(noin>1||noout>1)ok=false; if(ok)printf("Yes\n"); else printf("No\n"); } }
追記:ソース間違えたのではりなおしました。