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