PKU演習問メモ(11/2)
No. | 問題名 | 問題の種類および解法 | 難易度 |
---|---|---|---|
3170 | Knights of Ni | 幅優先探索 | ★★☆☆☆ |
1149 | PIGS | 最大流 | ★★★★☆ |
3045 | Cow Acrobats | 貪欲法 | ★★★★☆ |
3170 Knights of Ni
問題概要
解法
現在の位置を実拾ったかで多重化して幅優先探索。
ソースコード
int dy[]={-1,0,1,0},dx[]={0,1,0,-1}; int h,w,sq[1000][1000]; bool v[2][1000][1000]; int main() { scanf("%d%d",&w,&h); int y,x; rep(i,h)rep(j,w) { scanf("%d",sq[i]+j); if(sq[i][j]==2)y=i,x=j; } v[0][y][x]=1; queue<pi> Q; Q.push(mp(y*w+x,0)); while(!Q.empty()) { y=Q.front().first%(w*h)/w; x=Q.front().first%(w*h)%w; int f=Q.front().first/(w*h),c=Q.front().second; Q.pop(); rep(d,4) { int ny=y+dy[d],nx=x+dx[d],nf=f; if(ny<0||ny>=h||nx<0||nx>=w||sq[ny][nx]==1)continue; if(sq[ny][nx]==3) { if(f) { printf("%d\n",c+1); goto END; } continue; } if(sq[ny][nx]==4)nf=1; if(!v[nf][ny][nx])v[nf][ny][nx]=1,Q.push(mp(nf*w*h+ny*w+nx,c+1)); } } END:return 0; }
1149 PIGS
問題概要
解法
エッジをまとめる。
難易度弱気かも?Div1 Mediumないよな絶対。
ソースコード
void add(Graph &g,int s,int t,int w) { g[s].pb(Edge(s,t,w)); g[t].pb(Edge(t,s,0)); } bool f[100][1000]; int main() { int m,n,k,a; scanf("%d%d",&m,&n); Graph g(m+n+2); rep(i,m)scanf("%d",&a),add(g,0,i+1,a); rep(i,n) { scanf("%d",&k); rep(j,k)scanf("%d",&a),f[i][a-1]=1,add(g,a,i+m+1,inf); scanf("%d",&a); add(g,i+m+1,n+m+1,a); } rep(j,n)rep(i,j) { rep(k,m)if(f[i][k]&&f[j][k]) { add(g,i+m+1,j+m+1,inf); break; } } printf("%d\n",maximumFlow(g,0,n+m+1)); return 0; }
3045 Cow Acrobats
問題概要
解法
n=10くらいまでランダムケースで反例が見つからなかった。未証明。
ソースコード
int n,w[50000],s[50000]; pi t[50000]; int main() { scanf("%d",&n); rep(i,n)scanf("%d%d",w+i,s+i); rep(i,n)t[i]=mp(s[i]+w[i],i); sort(t,t+n); int W=0,ans=-inf; rep(i,n) { ans=max(ans,W-s[t[i].second]); W+=w[t[i].second]; } printf("%d\n",ans); return 0; }