PKU演習問メモ(11/1)

No.	問題名	問題の種類および解法	難易度
1195	Mobile phones	Binary Indexed Tree	★★★☆☆
1087	A Plug for UNIX	最大流	★★☆☆☆
2378	Tree Cutting	木DP	★★☆☆☆

1195 Mobile phones

問題概要

解法

二次元BITの作り方がわからなかったのでBITを1024個並べたら通ってしまった（酷
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
↑後で読む

ソースコード

int bit[1024][1025],n;
int sum(int y,int i){
	int s=0;
	for(;i>0;i-=i&-i)s+=bit[y][i];
	return s;
}
void add(int y,int i,int x)
{
	for(;i<=n;i+=i&-i)bit[y][i]+=x;
}

int main()
{
	int is,a,b,c,d; scanf("%d%d",&is,&n);
	while(scanf("%d",&is),is!=3)
	{
		if(is==1)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(b,a+1,c); continue;
		}
		int s=0;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		for(int y=b;y<=d;y++)s+=sum(y,c+1)-sum(y,a);
		printf("%d\n",s);
	}
	return 0;
}

1087 A Plug for UNIX

問題概要

解法

最大流。変換機は無限に使えることに注意しないとWA.

ソースコード

void add(Graph &g,int s,int t,int w)
{
	g[s].pb(Edge(s,t,w)); g[t].pb(Edge(t,s,0));
}

int n,m,k;
vector<string> vs;
map<string,int> id;

int main()
{
	int e[300][300]={0}; int l=2; //0:source 1:sink
	
	string s,t;
	cin>>n;
	rep(i,n)
	{
		cin>>s,id[s]=l++;
		e[id[s]][1]++;
	}
	cin>>m;
	rep(i,m)
	{
		cin>>t>>s;
		if(!id.count(s))id[s]=l++;
		e[0][id[s]]++;
	}
	cin>>k;
	rep(i,k)
	{
		cin>>s>>t;
		e[id[s]][id[t]]=inf;
	}
	
	Graph g(l);
	rep(i,l)rep(j,l)if(e[i][j])add(g,i,j,e[i][j]);
	
	cout<<m-maximumFlow(g,0,1)<<endl;
	
	return 0;
}

2378 Tree Cutting

問題概要

解法

ある頂点のサブツリーの頂点数をdp[i]とすると、O(n)でdpが求まる。
頂点が条件を満たす⇔その頂点から伸びる頂点以下のサブツリーの頂点数がn/2以下。

ソースコード

int n,dp[10000],ans[10000],na;
vector<vi> e;

void rec(int c,int p)
{
	dp[c]=1;
	fr(i,e[c])if(*i!=p)rec(*i,c),dp[c]+=dp[*i];
	if(n-dp[c]>n/2)return;
	fr(i,e[c])if(*i!=p&&dp[*i]>n/2)return;
	ans[na++]=c;
}

int main()
{
	scanf("%d",&n); int a,b;
	e.resize(n);
	rep(i,n-1)
	{
		scanf("%d%d",&a,&b); a--; b--;
		e[a].pb(b); e[b].pb(a);
	}
	rec(0,-1); sort(ans,ans+na);
	rep(i,na)printf("%d\n",ans[i]+1);
	
	return 0;
}