acm编程作业练习题

杭电：

1000A+BProblem4

1001SumProblem5

1002A+BProblemII6

1005NumberSequence8

1008Elevator9

1009FatMouse'Trade11

1021FibonacciAgain13

1089A+BforInput-OutputPractice(I)14

1090A+BforInput-OutputPractice(II)15

1091A+BforInput-OutputPractice(III)16

1092A+BforInput-OutputPractice(IV)17

1093A+BforInput-OutputPractice(V)18

1094A+BforInput-OutputPractice(VI)20

1095A+BforInput-OutputPractice(VII)21

1096A+BforInput-OutputPractice(VIII)22

1176免费馅饼23

1204糖果大战25

1213HowManyTables26

2000ASCH码排序32

2001计算两点间的距离34

2002计算球体积35

2003求绝对值36

2004成绩转换37

2005第几天？38

2006求奇数的乘积40

2007平方和与立方和41

2008数值统计42

2009求数列的和43

2010水仙花数44

2011多项式求和46

2012素数判定47

2014青年歌手大奖赛一评委会打分49

2015偶数求和50

2016数据的交换输出52

2017字符串统计54

2019数列有序!55

2020绝对值排序56

2021发工资咯：)58

2033人见人爱A+B59

2037今年暑假不AC61

2039三角形63

2040亲和数64

2045不容易系列之(3)——LELE的RPG难题65

2049不容易系列之(4)——考新郎66

2056Rectangles68

2073无限的路69

2084数塔71

2201熊猫阿波的故事72

2212DFS73

2304ElectricalOutlets74

2309ICPCScoreTotalizerSoftware75

2317NastyHacks77

2401BasketsofGoldCoins78

2500做一个正气的杭电人79

2501Tiling_easyversion80

2502月之数81

2503a/b+c/d82

2504又见GCD83

2519新生晚会84

2520我是菜鸟，我怕谁85

2521反素数86

2522Asimpleproblem88

2523SORTAGAIN89

2524矩形A+B90

2535Vote91

25378球胜负93

2539点球大战95

2547无剑无我98

2548两军交锋99

2549壮志难酬100

2550百步穿杨101

2551竹青遍野103

2552三足鼎立104

2553N皇后问题105

2554N对数的排列问题106

2555人人都能参加第30届校田径运动会了107

2560Buildings110

2561第二小整数112

2562奇偶位互换113

2563统计问题114

2564词组缩写115

2565放大的X117

2566统计硬币118

2567寻梦119

2568前进121

2569彼岸123

2700Parity124

2577HowtoType126

北京大学：

1035Spellchecker129

1061青蛙的约会133

1142SmithNumbers136

1200CrazySearch139

1811PrimeTest141

2262Goldbach'sConjecture146

2407Relatives150

2447RSA152

2503Babelfish156

2513ColoredSticks159

ACM算法：

kurXX最小生成树163

Prim164

堆实现最短路166

最短路DIJ普通版167

floyd168

BELL_MAN168

拓扑排序169

DFS强连通分支170

最大匹配172

还有两个最大匹配模板173

最大权匹配,KM算法175

两种欧拉路177

无向图：177

有向图：178

【最大流】EdmondsKarp178

dinic179

【最小费用最大流】EdmondsKarp对偶算法181

ACM题目：

【题目】排球队员站位问题182

【题目】把自然数N分解为若干个自然数之和。184

【题目】把自然数N分解为若干个自然数之积。185

【题目】马的遍历问题。185

【题目】加法分式分解。186

【题目】地图着色问题189

【题目】放置方案191

【题目】找迷宫的最短路径。194

【题目】火车调度问题195

【题目】农夫过河。197

【题目】七段数码管问题。199

【题目】求相邻的格的数不连续200

【题目】棋盘上放棋子202

【题目】迷宫问题204

【题目】一笔画问题205

【题目】城市遍历问题207

【题目】棋子移动问题208

【题目】求集合元素问题(l,2x+l,3X+l类)209

杭电：

1000A+BProblem

ProblemDescription

CalculateA+B.

Input

EachlinewillcontaintwointegersAandB.Processtoendoffile.

Output

Foreachcase,outputA+8inoneline.

SampleInput

ii

SampleOutput

2

Author

HDOJ

代码：

#include<stdio.h>

intmain()

inta,b;

while(scanf("%d%d",&a,&b)•=EOF)

printf("%d\n",a+b);

}

1001SumProblem

ProblemDescription

Hey,welcometoHDOJ(HangzhouDianziUniversityOnlineJudge).

Inthisproblem,yourtaskistocalculateSUM(n)=1+2+3+...+n.

Input

Theinputwillconsistofaseriesofintegersn,oneintegerperline.

Output

Foreachcase,outputSUM(n)inoneline,followedbyablankline.Youmayassumetheresult

willbeintherangeof32-bitsignedinteger.

SampleInput

i

100

SampleOutput

i

5050

Author

DOOMIII

解答：

#include<stdio.h>

main()

(

intn,i,sum;

sum=0;

while((scanf("％d"，&n)!=-l))

sum=O;

for(i=0;i<=n;i++)

sum+=i;

printf(n%d\n\nu,sum);

)

)

1002A+BProblemII

ProblemDescription

Ihaveaverysimpleproblemforyou.GiventwointegersAandB,yourjobistocalculatethe

SumofA+B.

Input

ThefirstlineoftheinputcontainsanintegerT(l<=T<=20)whichmeansthenumberoftestcases.

ThenTlinesfollow,eachlineconsistsoftwopositiveintegers,AandB.Noticethattheintegers

areverylarge,thatmeansyoushouldnotprocessthembyusing32-bitinteger.Youmayassume

thelengthofeachintegerwillnotexceed1000.

Output

Foreachtestcase,youshouldoutputtwolines.Thefirstlineis"Case##meansthenumberof

thetestcase.Thesecondlineistheanequation"A+B=Sum",SummeanstheresultofA+B.

Notetherearesomespacesinttheequation.Outputablanklinebetweentwotestcases.

SampleInput

2

12

112233445566778899998877665544332211

SampleOutput

Case1:

1+2=3

Case2:

112233445566778899+998877665544332211=1111111111111111110

Author

Ignatius.L

代码：

♦include<stdio.h>

♦include<string.h>

intmain(){

charstrl[1001]rstr2[1001];

inttri,len__str1,len_str2rlen__max,num=1,k;

scanf&t);

getchar();

while(t——){

inta[1001]={0},b[1001]={0},c[1001]={0};

scanf("%s"，strl);

len_strl=strlen(strl);

for(i=0;i<=len_strl-1;++i)

a[i]=strl[len_strl-1-i]-*0*;

scanf(”％s”，str2);

len__str2=strlen(str2);

for(i=0;i<=len_str2-1;++i)

b[i]=str2[len_str2-1-i]-'O';

if(len_str1>len_str2)

len_max=len_str1;

else

len_max=len_str2;

k=0;

for(i=0;i<=len__max-1;++i){

c[i]=(a[i]+b[i]+k)%10;

k=(a[i]+b[i]+k)/10;

)

if(k!=0)

c[len_max]=1;

printf(HCase%d:\nH,num);

num++;

printf(H%s+%s=H,strl,str2);

if(c[len_max]==1)

printf(nln);

for(i=len_max-1;i>=0;-i){

printf(n%dn,c[i]);

)

printf(n\nn);

if(t>=1)

printf(n\nH);

)

return0;

1005NumberSequence

ProblemDescription

Anumbersequenceisdefinedasfollows:

f(l)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.

GivenA,B,andn,youaretocalculatethevalueoff(n).

Input

Theinputconsistsofmultipletestcases.Eachtestcasecontains3integersA,Bandnonasingle

line(1<=A,B<=1000,1<=n<=100,000,000).Threezerossignaltheendofinputandthistest

caseisnottobeprocessed.

Output

Foreachtestcase,printthevalueoff(n)onasingleline.

SampleInput

113

1210

000

SampleOutput

2

5

Author

CHEN,Shunbao

Source

ZJCPC2004

Recommend

JGShining

代码：

#include<stdio.h>

intf[200];

intmain()

(

inta,b,n,i;

while(scanf(”％d%d%d”，&a,&b,&n)&&a&&b&&n)

{

if(n>=3)

(

f[2]=1;

for(i=3;i<=200;i++)

(

f[i]=(a*f[i-2])%7;

if(f[i-l]==l&&f[i]==l)

break;

)

i-=2；

n=n%i;

if(n==0)

printf("%d\nf,,f[i]);

else

HH

printf(%d\nzf[n]);

}

else

printf(Hl\nu);

)

return0;

1008Elevator

ProblemDescription

Thehighestbuildinginourcityhasonlyoneelevator.ArequestlistismadeupwithNpositive

numbers.Thenumbersdenoteatwhichfloorstheelevatorwillstop,inspecifiedorder.Itcosts6

secondstomovetheelevatoruponefloor,and4secondstomovedownonefloor.Theelevator

willstayfbr5secondsateachstop.

Foragivenrequestlist,youaretocomputethetotaltimespenttofulfilltherequestsonthelist.

TheelevatorisontheOthflooratthebeginninganddoesnothavetoreturntothegroundfloor

whentherequestsarefulfilled.

Input

Therearemultipletestcases.EachcasecontainsapositiveintegerN,followedbyNpositive

numbers.Allthenumbersintheinputarelessthan100.AtestcasewithN=0denotestheendof

input.Thistestcaseisnottobeprocessed.

Output

Printthetotaltimeonasinglelinefbreachtestcase.

SampleInput

12

3231

0

SampleOutput

17

41

Author

ZHENG,Jianqiang

Source

ZJCPC2004

Recommend

JGShining

代码：

#include<stdio.h>

inta[110];

intmain()

(

intsum,i,n;

while(scanf("％d”，&n)&&n!=0)

(

for(i=l;i<=n;i++)

nH

scanf(%dz[i]);

sum=0;

a[0]=0;

for(i=l;i<=n;i++)

(

if(a[i]>a[i-lj)

sum+=6*(a[i]-a[i-l]);

else

sum+=4*(a[i-l]-a[i]);

sum+=5;

)

printf("％d\n"，sum);

)

return0;

)

1009FatMouse，Trade

ProblemDescription

FatMousepreparedMpoundsofcatfood,readytotradewiththecatsguardingthewarehouse

containinghisfavoritefood,JavaBean.

ThewarehousehasNrooms.Thei-throomcontainsJ[i]poundsofJavaBeansandrequiresF[i]

poundsofcatfood.FatMousedoesnothavetotradeforalltheJavaBeansintheroom,instead,he

maygetJ[i]*a%poundsofJavaBeansifhepaysF[i]*a%poundsofcatfood.Hereaisareal

number.Nowheisassigningthishomeworktoyou:tellhimthemaximumamountofJavaBeans

hecanobtain.

Input

Theinputconsistsofmultipletestcases.Eachtestcasebeginswithalinecontainingtwo

non-negativeintegersMandN.ThenNlinesfollow,eachcontainstwonon-negativeintegersJ[i]

andF[i]respectively.Thelasttestcaseisfollowedbytwo-l's.Allintegersarenotgreaterthan

1000.

Output

Foreachtestcase,printinasinglelinearealnumberaccurateupto3decimalplaces,whichisthe

maximumamountofJavaBeansthatFatMousecanobtain.

SampleInput

53724352203251824151510-1-1

SampleOutput

13.33331.500

Author

CHEN,Yue

Source

ZJCPC2004

Recommend

JGShining

代码：

#include<stdio.h>

#include<string.h>

#defineMAX1000

intmain()

{

inti,j,m,n,temp;

intJ[MAX],F[MAX];

doubleP[MAX];

doublesum,templ;

scanff%d%d”,&m,&n);

while(m!=-l&&n!=-l)

{

sum=0;

memset(J,0,MAX*sizeof(int));

memset(F,0,MAX*sizeof(int));

memset(P,0,MAX*sizeof(double));

fbr(i=0;i<n;i++){scanf("%d%d",&J[i],&F[i]);P[i]=J[i]*1.0/((double)F[i]);}

for(i=0;i<n;i++)

(

fdr(j=i+1j<n;j++)

{

if(P[i]<PD])

{

templ=P[i];P[i]=P[j];P[j]=templ;

temp=J[i];J[i]=JU];J[j]=temp;

temp=F[i];F[i]=F[j];F[j]=temp;

)

)

)

fbr(i=0;i<n;i++)

(

if(m<F[i]){sum+=m/((double)F[i])*J[i];break;}

else{sum+=J[i];m-=F[i];}

)

printf("%.31f\n",sum);scanf("%d%d",&m,&n);

}

return0;

1021FibonacciAgain

ProblemDescription

ThereareanotherkindofFibonaccinumbers:F(0)=7,F(l)=11,F(n)=F(n-l)+F(n-2)(n>=2).

Input

Inputconsistsofasequenceoflines,eachcontaininganintegern.(n<1,000,000).

Output

Printtheword"yes"if3divideevenlyintoF(n).

Printtheword"no"ifnot.

SampleInput

o

i

2

3

4

5

SampleOutput

no

no

yes

no

no

no

Author

Leojay

Recommend

JGShining

#include<stdio.h>

intmain()

(

longn;

while(scanf(n%ldn,&n)!=EOF)

if(n%8==2||n%8==6)

printf(nyes\n");

else

printf(Hno\n");

return0;

)

1089A+BforInput-OutputPractice

⑴

ProblemDescription

YourtaskistoCalculatea+b.

Tooeasy?!Ofcourse!Ispeciallydesignedtheproblemforacmbeginners.

Youmusthavefoundthatsomeproblemshavethesametitleswiththisone,yes,allthese

problemsweredesignedforthesameaim.

Input

Theinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairof

integersperline.

Output

Foreachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwith

onelineofoutputforeachlineininput.

SampleInput

15

1020

SampleOutput

6

30

Author

icy

Recommend

JGShining

解答:

#include<stdio.h>

main()

inta,b;

while(scanf(”％d%d”，&a,&b)!=EOF)

printf("%d\n"，a+b);

)

1090A+BforInput-OutputPractice

(ID

ProblemDescription

YourtaskistoCalculatea+b.

Input

InputcontainsanintegerNinthefirstline,andthenNlinesfollow.Eachlineconsistsofapairof

integersaandb,separatedbyaspace,onepairofintegersperline.

Output

Foreachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwith

onelineofoutputfbreachlineininput.

SampleInput

2

15

1020

SampleOutput

6

30

Author

ley

Recommend

JGShining

解答：

#include<stdio.h>

#defineM1000

voidmain()

inta,b,n,j[M],i;

//printf("pleaseinputn:\n");

scanf("%d",&n);

for(i=0;i<n;i++)

(

scanf("%d%d",&a,&b);

//printf("%d%d",a,b);

j[i]=a+b;

)

i=0;

while(i<n)

(

printf("%d",j[i]);

i++；

printf("\n");

)

}

1091A+BforInput-OutputPractice

(III)

ProblemDescription

YourtaskistoCalculatea+b.

Input

Inputcontainsmultipletestcases.Eachtestcasecontainsapairofintegersaandb,onepairof

integersperline.Atestcasecontaining00tenninatestheinputandthistestcaseisnottobe

processed.

Output

Foreachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwith

onelineofoutputforeachlineininput.

SampleInput

15

1020

00

SampleOutput

6

30

Author

ley

Recommend

JGShining

解答：

#include<stdio.h>

main()

(

inta,b;

scanf(n%d

while(!(a==0&&b==0))

(

printf(n%d\n\a+b);

scanf(n%d

)

)

1092A+BforInput-OutputPractice

(IV)

ProblemDescription

YourtaskistoCalculatethesumofsomeintegers.

Input

Inputcontainsmultipletestcases.EachtestcasecontainsaintegerN,andthenNintegersfollow

inthesameline.Atestcasestartingwith0terminatestheinputandthistestcaseisnottobe

processed.

Output

Foreachgroupofinputintegersyoushouldoutputtheirsuminoneline,andwithonelineof

outputforeachlineininput.

SampleInput

41234

512345

0

SampleOutput

io

15

Author

ley

Recommend

JGShining

解答：

♦include<stdio.h>

intmain()

(

intn,sum,i,t;

while(scanf(n%dn,&n)!=E0F&&n!=0)

(

sum=0;

for(i=0;i<n;i++)

(

scanf("％d"，&t);

sum=sum+t;

}

printf(H%d\nn,sum);

)

)

1093A+BforInput-OutputPractice

(V)

ProblemDescription

Yourtaskistocalculatethesumofsomeintegers.

Input

InputcontainsanintegerNinthefirstline,andthenNlinesfollow.Eachlinestartswithainteger

M,andthenMintegersfollowinthesameline.

Output

Foreachgroupofinputintegersyoushouldoutputtheirsuminoneline,andwithonelineof

outputforeachlineininput.

SampleInput

2

41234

512345

SampleOutput

io

15

Author

ley

解答：

#include<stdio.h>

main()

(

intn,a,b,i,j,sum;

sum=0;

while(scanf(n%d\n",&n)!=-l)

(

for(i=0;i<n;i++)

(

scanf(n%dn,&b);

for(j=0;j<b;j++)

(

scanf(，&a);

sum+=a;

)

printf("%d\nH,sum);

sum=0;

)

}

)

1094A+BforInput-OutputPractice

(VI)

ProblemDescription

Yourtaskistocalculatethesumofsomeintegers.

Input

Inputcontainsmultipletestcases,andonecaseoneline.EachcasestartswithanintegerN,and

thenNintegersfollowinthesameline.

Output

ForeachtestcaseyoushouldoutputthesumofNintegersinoneline,andwithonelineofoutput

foreachlineininput.

SampleInput

41234

512345

SampleOutput

io

15

Author

ley

Recommend

JGShining

解答：

#include<stdio.h>

main()

(

intn,a,b,i,j,sum;

sum=0;

while(scanf(n%d\nH,&n)!=-l)

(

for(j=0;j<n;j++)

(

scanf("%d",&a);

sum+=a;

)

printf("%d\n",sum);

sum=O;

}

)

[CopytoClipboard][SavetoFile]

1095A+BforInput-OutputPractice

(VII)

ProblemDescription

YourtaskistoCalculatea+b.

Input

Theinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairof

integersperline.

Output

Foreachpairofinputintegersaandbyoushouldoutputthesumofaandb,andfollowedbya

blankline.

SampleInput

15

1020

SampleOutput

6

30

Author

ley

Recommend

JGShining

解答：

#include<stdio.h>

main()

inta,b;

while(scanf(=％d%d”，&a,&b)!=EOF)

printf("％d\n\n”，a+b);

}

1096A+BforInput-OutputPractice

(VIII)

ProblemDescription

Yourtaskistocalculatethesumofsomeintegers.

Input

InputcontainsanintegerNinthefirstline,andthenNlinesfollow.Eachlinestartswithainteger

M,andthenMintegersfollowinthesameline.

Output

Foreachgroupofinputintegersyoushouldoutputtheirsuminoneline,andyoumustnotethat

thereisablanklinebetweenoutputs.

SampleInput

3

41234

512345

3123

SampleOutput

io

15

6

Author

ley

Recommend

JGShining

解答：

intmain()

(

inta,bzi,jr1[1000]fk;

scanf("％d“，&i);

getchar();

for(j=l;j<=i;j++)

l[j]=0；

for(j=l;j<=i;j++)

(

scanf("%d",&a);

getchar();

for(k=l;k<=a;k++)

(

scanf("%d",&b);

getchar();

1[j]+=b;

}

}

for(j=l;j<=i-l;j++)

printf("%d\n\n",l[j]);

printf("%d\n",1[i]);

1176免费馅饼

ProblemDescription

都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的

馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范

围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但

由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游

戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动

不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

.|——I——I——I——I_A~।——I_I——I——I

01234—678910

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时

gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的

馅饼。问gameboy最多可能接到多少个馅饼？(假设他的背包可以容纳无穷多个馅饼)

Input

输入数据有多组。每组数据的第一行为以正整数n(0<n<100000),表示有n个馅饼掉在这条

小径上。在结下来的n行中，每行有两个整数x,T((XT<1000()()),表示在第T秒有一个馅饼掉

在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。

Output

每一组输入数据对应一行输出。输出一个整数m,表示gameboy最多可能接到m个馅饼。

提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。

SampleInput

65141617272830

SampleOutput

4

Author

Iwg

代码：

#include<stdio.h>

#include<string.h>

#defineMAX100001

intarr[MAX][13];

intMax(intnl,intn2,intn3)

(

intmax;

max=(nl>n2)?n1:n2;

max=(max>n3)?max:n3;

returnmax;

)

voidres(intnum)

(

intij;

intn,m,count=-l;

memset(arr,O,MAX*13*sizeof(int));

fbr(i=0;i<num;i++)

(

scanfC%d%d”,&n,&m);

arr[m][n+l]4-+;

ifi(count<m)count=m;

)

for(i=count-l;i>=0;i—)

for(j=l；j<=ll；j++)

arr[i][j]+=Max(arr[i+1][j-1],arr[i+l][j],arr[i+1]U+1]);

printf("%d\n",arr[0][6]);

)

intmain()

(

intnum;

scanf(n%dn,&num);

while(num)

res(num);

scanf(”％d”,&iium);

)

return0;

}

1204糖果大战

ProblemDescription

生日Party结束的那天晚上，剩下了一些糖果，Gandon想把所有的都统统拿走，Speakless

于是说：“可以是可以，不过我们来玩24点，你不是已经拿到了一些糖果了吗？这样，如果

谁赢一局，就拿走对方一颗糖，直到拿完对方所有的糖为止。“如果谁能算出来而对方算不

出来，谁就赢，但是如果双方都能算出或者都不能，就算平局，不会有任何糖果的得失。

Speakless是个喜欢提前想问题的人，既然他发起了这场糖果大战，就自然很想赢啦(不然

可就要精光了-二)。现在他需要你的帮忙，给你他每局赢的概率和Gardon每局赢的概率，

请你给出他可能获得这场大战胜利的概率。

Input

每行有四个数，Speakless手上的糖果数N、Gardon手上的糖果数M(0<=N,M<=50)、一局

Speakless能解答出来的概率p、一个问题Gardon能解答出来的概率q(0〈=p,q〈=l)。

Output

每行一个数，表示Speakless能赢的概率(用百分比计算，保留到小数点后2位)。

SampleInput

50500.50.510100.510.550500.510.5

SampleOutput

0.500.600.88

Author

Spcakless

Source

Gardon-DYGGContest2

Recommend

JGShining

代码：

#include<stdio.h>

#include<math.h>

constdoubleEPS=le-12;

inlinevoidsolve(intn,intm,doublep,doubleq)

{

if(n=0)printf(n0.00\nn);

elseif(m==0)printf("1.00\n");

elseif(p=0.0||q=1.0)printf(,,0.00\nH);

else

doublelamda=q*(l-p)/(p*(l-q));

if(fabs(lamda-1.0)<EPS)pdntf(”％.21f\n"，double(n)/(m+n));

else

doubleres=(l-pow(lainda,n))/(l-pow(lamda,m+n));

printf("%.21f\nn,res);

}

}

}

intmain()

{

intn,m;

doublep,q;

while(scanf(,,%d%d%lf%lf,,&n,&m,&p,&q)!=EOF){

solve(n,m,p,q);

}

return0;

)

1213HowManyTables

ProblemDescription

TodayisIgnatius*birthday.Heinvitesalotoffriends.Nowit'sdinnertime.Ignatiuswantsto

knowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweach

other,andallthefriendsdonotwanttostaywithstrangers.

OneimportantrulefbrthisproblemisthatifItellyouAknowsB,andBknowsC,thatmeansA,

B,Cknoweachother,sotheycanstayinonetabic.

Forexample:IfItellyouAknowsB,BknowsC,andDknowsE,soA,B,Ccanstayinone

table,andD,Ehavetostayintheotherone.SoIgnatiusneeds2tablesatleast.

Input

TheinputstartswithanintegerT(1<=T<=25)whichindicatethenumberoftestcases.ThenTtest

casesfollow.EachtestcasestartswithtwointegersNandM(l<=N,M<=1000).Nindicatesthe

numberoffriends,thefriendsaremarkedfrom1toN.ThenMlinesfollow.Eachlineconsistsof

twointegersAandB(A!=B),thatmeansfriendAandfriendBknoweachother.Therewillbea

blanklinebetweentwocases.

Output

Foreachtestcase,justoutputhowmanytablesIgnatiusneedsatleast.DoNOTprintanyblanks.

SampleInput

2531223455125

SampleOutput

24

Author

Ignatius.L

Source

杭电ACM省赛集训队选拔赛之热身赛

Recommend

Eddy

代码：#include<stdio.h>

#defineMAX2000

intn,m;

intstart[MAX],end[MAX];

intres;

intarr[MAX];

intlen;

intMempty()

(

inti;

fbr(i=0;i<m;i++)

if^start[i]!=O)return0;

return1;

}

intinSet(intindex)

{

inti;

fbr(i=O;i<res;i-H-)

if{arr[i]=index)return1;

return0;

}

voiddeal()

{

inti;

intspace=0;

for(i=0;i<m;i++)

{

if(start[i]=O)space++;

else{start[i-space]=start[i];end[i-space]=end[i];

}

m=m-space;

}

voidproc()

{

inti;intj;

while(!Mempty())

i=0;

while(i<m)

(

if(start[i]=O){i-H-;continue;}

if(i=0)

{

if(start[i]!=end[i]){arr[res-H-]=start[i];arr[res++]=end[i];

elsearr[res++]=start[i];

start[i]=end[i]=O;

}

else

{

fbr(j=O;j<res;j++)

{

if(arr[j]=start[i])

{

if(!inSet(end[i]))arr[res+4-]=end[i];

start[i]=end[i]=O;

i=-l；

break;

)

if(arr[j]==end[i])

{

if(!inSet(start[i]))arr[res++]=start[i];

start[i]=end[i]=O;

i=-l；

break;

i++；

}

len++;deal();

)

if(res=n)len—;

elselen+=n-res-l;

}

intmain()

{

inti;

intnum;

scanf(M%dn,&num);

while(num—)

scanf(,,%d%d,,,&n,&m);

for(i=O;i<m;i++)scanff%d%d",&start[i],&end[i]);

res=O;len=O;proc();