首页 > ACM题库 > HDU-杭电 > HDU 3957-Street Fighter[解题报告]HOJ
2015
04-14

HDU 3957-Street Fighter[解题报告]HOJ

Street Fighter

问题描述 :

Street Fighter is a popular Fighting game. In the game, you could choose many roles to fight.
Each role has some models, in different model the role has different super skill. Such as Ryu, he has two model — "Metsu Hadoken" and "Metsu Shoryuken". In "Metsu Hadoken" model, Ryu could beat Chun-Li easyly and in "Metsu Shoryuken" he could beat Ken.
SanguoSHA

Giving the information of which role in which model could beat which role in which model. Your task is choosing minimum roles in certain model to beat other roles in any model.(each role could only be chosen once)

输入:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains a integers N(2<=N<=25), indication the number of roles. (roles numbered from 0 to N – 1).
Then N blocks follow, each block contain the information of a role.
The first of each block contains a integer M(1<=M<=2), indication the number of model of this role.(models numbered from 0 to M – 1)
Then M lines follow, each line contain a number K(1<=K<=10), then K pairs integers(role id and model id) follow, indicating the current role in this model could beat that role in such model.

输出:

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains a integers N(2<=N<=25), indication the number of roles. (roles numbered from 0 to N – 1).
Then N blocks follow, each block contain the information of a role.
The first of each block contains a integer M(1<=M<=2), indication the number of model of this role.(models numbered from 0 to M – 1)
Then M lines follow, each line contain a number K(1<=K<=10), then K pairs integers(role id and model id) follow, indicating the current role in this model could beat that role in such model.

样例输入:

2
2
2
1 1 0
1 1 1
2
1 0 0
1 0 1

4
2
2 1 0 1 1
1 2 0
2
2 3 0 0 1
1 2 0
2
2 0 0 0 1
1 1 0
2
2 2 0 2 1
1 1 0

样例输出:

Case 1: 2
Case 2: 2
Hint
In the first sample, you must select all of roles, because one role couldn't beat the other role in any model. In the second sample, you can select role 0 with its model 0, and role 3 with its model 0, then role 1 and role 2 will to be defeated no matter which model they use.

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define max_node 100010
#define inf 0xfffffff
int total;
int R[max_node];
int L[max_node];
int U[max_node];
int D[max_node];
int col[max_node];
int row[max_node];
int h[110];//s[C]
int s[110];//h[R]
bool vis[max_node];
void initDL(int c)
{
	memset(h,-1,sizeof(h));
	memset(s,0,sizeof(s));
	for(int i=0;i<=c;i++)
	{
		D[i]=U[i]=i;
		L[i+1]=i;
		R[i]=i+1;
	}
	R[c]=0;
	total=c+1;
}
void link(int r,int c)
{
//	printf("%d %d\n",r,c);
	s[c]++;
	row[total]=r;
	col[total]=c;
	U[total]=U[c];
	D[U[c]]=total;
	D[total]=c;
	U[c]=total;
	if(h[r] == -1)
		h[r]=L[total]=R[total]=total;
	else
	{
		L[total]=L[h[r]];
		R[L[h[r]]]=total;
		R[total]=h[r];
		L[h[r]]=total;
	}
	total++;
}
void remove(int c)
{
	for(int i=D[c];i!=c;i=D[i])
	{
		L[R[i]]=L[i];
		R[L[i]]=R[i];
	}
}
void resume(int c)
{
	for(int i=U[c];i!=c;i=U[i])
		L[R[i]]=R[L[i]]=i;
}
void removeEX(int c)
{
	L[R[c]]=L[c];
	R[L[c]]=R[c];
	for(int i=D[c];i!=c;i=D[i])
		for(int j=R[i];j!=i;j=R[j])
		{
			U[D[j]]=U[j];
			D[U[j]]=D[j];
			s[col[j]]--;
		}
}
void resumeEX(int c)
{
	for(int i=U[c];i!=c;i=U[i])
		for(int j=L[i];j!=i;j=L[j])
		{
			U[D[j]]=j;
			D[U[j]]=j;
			s[col[j]]++;
		}
	L[R[c]]=c;
	R[L[c]]=c;
}
int limit,bound;
int f()
{
	int ret=0;
	for(int i=R[0];i;i=R[i])
		vis[i]=true;
	for(int i=R[0];i && i <= bound;i=R[i])
		if(vis[i])
		{
			vis[i]=false;
			ret++;
			for(int j=D[i];j!=i;j=D[j])
				for(int k=R[j];k!=j;k=R[k])
					vis[col[k]]=false;
		}
	return ret;
}
void dance(int dep)
{
	if(dep+f() >= limit)
		return;
	if(R[0] == 0 || R[0] > bound)
	{
		limit=min(dep,limit);
		return;
	}
	int mm=inf;
	int c;
	for(int i=R[0];i && i <= bound;i=R[i])
		if(s[i] < mm)
		{
			mm=s[i];
			c=i;
		}
	for(int i=D[c];i!=c;i=D[i])
	{
		remove(i);
		for(int j=R[i];j!=i;j=R[j])
			if(col[j] <= bound)
				remove(j);
		for(int j=R[i];j!=i;j=R[j])
			if(col[j] > bound)
				removeEX(col[j]);
		dance(dep+1);
		for(int j=L[i];j!=i;j=L[j])
			if(col[j] > bound)
				resumeEX(col[j]);
		for(int j=L[i];j!=i;j=L[j])
			if(col[j] <= bound)
				resume(j);
		resume(i);
	}
}
struct Node
{
	int n;
	vector<int>x[2];
	vector<int>y[2];
	void in()
	{
		x[0].clear();
		x[1].clear();
		y[0].clear();
		y[1].clear();
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			int len;
			scanf("%d",&len);
			while(len--)
			{
				int a,b;
				scanf("%d %d",&a,&b);
				x[i].pb(a);
				y[i].pb(b);
			}
		}
	}
}p[110];
int id[110][110];
int main()
{
	int cas;
	scanf("%d",&cas);
	for(int cc=1;cc<=cas;cc++)
	{
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			p[i].in();
		int total=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<p[i].n;j++)
				id[i][j]=++total;
		initDL(total+n);
		bound=total;
		limit=total;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<p[i].n;j++)
			{
				link(id[i][j],total+i+1);
				for(int k=0;k<p[i].n;k++)
					link(id[i][j],id[i][k]);
				int len=p[i].x[j].size();
				for(int k=0;k<len;k++)
					link(id[i][j],id[p[i].x[j][k]][p[i].y[j][k]]);
			}
		}
		limit=total;
		dance(0);
		printf("Case %d: %d\n",cc,limit);
	}
	return 0;
}
/*
1
2
2
1 1 0
1 1 1
2
1 0 0
1 0 1
 */

  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  4. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  5. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }