这个是问题：
这里有一个非常著名的中国故事。“大约2300年以前，田忌将军是齐国高级官员，他喜欢和国王还有其它的人赛马”。“田忌和国王都有3匹不同档次的马，即普通的，好的，以及最好的。赛马的规则是在一次比赛中有三轮，每匹马必须跑一轮。输一轮比赛就要输掉200银元。”“作为国家里最具权威的国王，当然具有超级无敌的骏马，他的每一种档次的马都要比田忌的快。因此，国王每次都从田忌那里赢600银元。”“当然田忌心里是非常的郁闷的，这种状况直到他遇见了中国历史上非常有名的将军孙膑，才发生变化。田忌根据孙膑告诉他的一个小计谋，终于从国王那里赢回了200银元，并且在以后的比赛中，一直都保持了这个荣誉。”“这是一个非常简单的计谋。用他的普通马与国王最好的马进行比赛，当然他会输掉本轮角逐，然后，再用他的好马与国王的普通马对决，最后用他最好的马与国王的好马对决。这是一个多么简单的计谋呀，你是怎么看待中国历史上这位高级官员田忌的呢？” 如果田忌生活在现在，他一定会笑他自己的；而如果他在现在的ACM竞赛中，他会发现，在偶图中寻找最大配对非常容易就能发现赛马问题。把田忌的马画在一边，国王的马在另一边。当田忌的一匹马能够打败国王的一匹马时，我们就在这两匹马之间画一条边， 意味着我们希望建立这样的配对。于是，赛马赢得尽量多的轮次的问题就是在偶图中寻找尽可能多的配对。如果这里有更多的关系，问题就会变得复杂，他可以给所有可能的边都附上权值-1、0或1，再找到每种匹配的最大权值。然而，赛马问题是偶图匹配中的一个非常特殊的例子。这个图取决于马的速度，高速顶点打败低速顶点。本问题就是要你写一个程序，解决种种非常特殊的匹配。
Input
最多有50个测试用例。每一个用例的第一行是正整数 n (n
#include
int cmp(const void *p,const void *q)
{
return (*(int*)p)-*((int*)q);
}
int i,n,j,t,r,s,a[1000],b[1000];
void main()
{
while(scanf("%d",&n)!=EOF)
{t=0;
s=0;
j=0;
r=0;
if(n==0) break;
for(i=0;ib[j])
{a=0;b[j]=0;t++;j++;}
qsort(a,n,sizeof(a[0]),cmp);
qsort(b,n,sizeof(a[0]),cmp);
j=0;
for(i=0;i<n;i++)
if(a==b[j])
{j++;r++;}
s=n*-200+t*200+r*200;
printf("%d\n",s);
}
}
为什么？
|
