Summer Training 06 - Amritapuri 2012 总结
题意:
读了好久才明白它要干嘛……有1~N种魔法,一般编号大的赢编号小的,但是有M对是编号小的赢编号大的,没有传递性。
A先选一种魔法,如果接下来B无论选哪个都输给A,则输出2和A选的魔法编号。
如果A被B选的魔法打败了,而他能再选一种来打败B选的(B还用那个),那么输出1.
否则输出0.
假设A和B都是按最优策略选魔法,而且同一种魔法只能选一次。
题解:
假如一种魔法不回被别的魔法打败,则为2.
否则为1,因为如果B选的魔法即能打败A第一次选的,又不会被A第二次选的打败,说明这个魔法是无敌的,那A一开始就选这个就行了。
//Time:1450ms
//Memory:17408KB
//Length:785B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
#define MP(x,y) make_pair(x,y)
#define MAXN 1000010
set<pair<int,int> >se;
int num[MAXN];
bool vi[MAXN];
int main()
{
//freopen("/home/moor/Code/input","r",stdin);
int ncase,n,m,k,ans=0;
scanf("%d",&ncase);
while(ncase--)
{
bool flag=0;
scanf("%d%d",&n,&m);
se.clear();
memset(num,0,sizeof(num));
memset(vi,0,sizeof(vi));
for(int i=0;i<m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>b) swap(a,b);
if(se.find(MP(a,b))==se.end())
se.insert(MP(a,b)),++num[a],vi[b]=1;
}
for(int i=n;i>=1;--i)
if(num[i]==n-i&&!vi[i])
{
printf("2 %d\n",i);
flag=1;
break;
}
if(!flag)
printf("1\n");
}
return 0;
}