0%

做Good Bye 2014那个晚上做着练习的。

379A - New Year Candles:

这居然是协会十一时出的一道题,简单题不多说了。

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
int main(){
int a,b,left,cnt;
while(scanf("%d%d",&a,&b)!=EOF){
cnt=0;
for(left=a;left>=b;left-=b-1){
cnt+=b;
}
cnt+=left;
printf("%d\n",cnt);
}
}

379B - New Year Present:

输入钱包个数,和每个钱包需要放的硬币个数,指挥机器人放硬币,不能在同一个地方连续放,输出操作方法。

因为没有说是最少步数,只是限制在10^6以下,所以从左往右放直到放满所有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
const int maxn=310;
int a[maxn],cur,flag,sum,n;
void put_coin(){
if(a[cur]&&!flag){
flag=1,--a[cur],--sum;
putchar('P');
}
else if(a[cur]){
if(cur!=n-1){
putchar('R');
if(a[cur+1]){
--a[cur+1],--sum;
putchar('P');
}
--a[cur],--sum;
putchar('L');
putchar('P');
}
else{
putchar('L');
putchar('R');
putchar('P');
--a[cur],--sum;
}
}
else if(cur!=n-1){
flag=0,++cur;
putchar('R');
}
else{
flag=0,--cur;
putchar('L');
}
if(sum) put_coin();
}
int main(){
while(scanf("%d",&n)!=EOF){
cur=flag=sum=0;
memset(a,0,sizeof(a));
for(int i=0;i<n;++i){
scanf("%d",&a[i]);
sum+=a[i];
}
put_coin();
putchar('\n');
}
return 0;
}

379C - New Year Ratings Change:

输入人数和每个人当前的rating,求变动后rating,要求不能有人rating相同。

一开始超时了好多次,Ac的这次764ms,也不是很理想。

排序以后为每个人的rating赋值,赋他当前的rating或者之前rating的最大值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=300010;
struct rating{
int res,num,rate;
rating(int res=0,int num=0):res(res),num(num),rate(0){}
};
rating a[maxn];
bool cmp1(rating a,rating b){
return a.res<b.res;
}
bool cmp2(rating a,rating b){
return a.num<b.num;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
int k;
scanf("%d",&k);
a[i]=rating(k,i);
}
sort(a,a+n,cmp1);
int last=0;
for(int i=0;i<n;i++){
if(last>=a[i].res){
a[i].rate=last;
++last;
}
else{
a[i].rate=a[i].res;
last=a[i].res+1;
}
}
sort(a,a+n,cmp2);
for(int i=0;i<n;i++){
if(i) printf(" ");
printf("%d",a[i].rate);
}
printf("\n");
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

做了前三道,感觉这次的前三道不是很难。

507A - Amr and Music:

学乐器,给出乐器数、天数和每个乐器需要的天数。求能学会哪几个。

结构体排序,输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct course{
int a,b;
course(int a=0,int b=0):a(a),b(b){}
bool operator < (const course& x) const {
return b<x.b;
}
};
vector<course> a;
vector<int> b;
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i){
int t;
scanf("%d",&t);
a.push_back(course(i,t));
}
sort(a.begin(),a.end());
int p=0;
while(1){
if(a[p].b<=k){
k-=a[p].b;
b.push_back(a[p].a+1);
++p;
}
else break;
if(p==n) break;
}
printf("%d\n",(int)b.size());
for(int i=0;i<b.size();++i){
if(i) printf(" ");
printf("%d",b[i]);
}
return 0;
}

507B - Amr and Pins:

输入圆的半径初始位置、目标位置。求转移需要的最少的次数。

很容易想思路,一次最长能转移的距离等于直径,求位置之间的距离。然后除以直径向上取整。

1
2
3
4
5
6
7
8
9
#include<cstdio>
#include<cmath>
int main(){
double r,x,y,ax,ay,l;
scanf("%lf%lf%lf%lf%lf",&r,&x,&y,&ax,&ay);
l=sqrt((x-ax)*(x-ax)+(y-ay)*(y-ay));
printf("%d",(int)ceil(l/r/2));
return 0;
}

507C - Guess Your Way Out!:

给出完全二叉树的深度,和目标叶子的编号。求在LRLRLR规则下,到目标叶片之前会经过多少叶子。

每走一层就判断是加整个子树再加一还是只加一,因为如果目标方向与当前左右方向不一致,必定要遍历另一棵子树,相同则只需走一个。

同时让n等于在当前子树中的编号。走到第h层就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
int h,cur=0;
long long n,k=0,x=1;
cin>>h>>n;
bool l=true;
while(cur!=h){
if(n>(x<<(h-cur-1))){
n-=x<<(h-cur-1);
if(l) k+=x<<(h-cur);
else{++k;l=!l;}
}
else{
if(l){++k;l=!l;}
else k+=x<<(h-cur);
}
++cur;
}
cout<<k;
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

终于把紫书刷完一百道了,按教主说的,反正首先这个诚意是有了,可以在机房分配座位了。

从2014.10.12开始112天了,总算结束了这个任务了。。

总感觉之前刷题过于追求题数,有的题其实还没理解就跟着书上生扯出来了;还有的就是水过去了,卡着时间过的。

以后准备先重看紫书前几章,把巩固知识基础。然后再来回顾自己之前做的题,看看别人的解题思路,拓展下思维,顺便把博客分类再按照知识点理一理。再后慢慢看紫书后几章 ,同时看看算法导论。

又是一个新的开始。

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

昨天整理了博客目录,看紫书第九章还没有做的题,就翻书看到了这道水题。

给出r*c的数表代表每个地点的高度,滑雪时高度要严格降低,求最长滑雪路径。

记忆化搜索最长路径,将每个点的最长路径存在数组g中,算完一个点比较维护最长路径就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn=110;
const int x[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int h[maxn][maxn],g[maxn][maxn];
int dp(int a,int b){
if(g[a][b]>=0) return g[a][b];//计算过的值直接使用。
bool flag=0;
for(int i=0;i<4;++i)
if(h[a][b]>h[a+x[i][0]][b+x[i][1]]&&h[a+x[i][0]][b+x[i][1]]!=-1){
g[a][b]=max(dp(a+x[i][0],b+x[i][1])+1,g[a][b]);//求当前点的最长滑雪路径。
flag=1;
}
if(!flag) return 0;//无法滑倒其他点路径长为0。
return g[a][b];
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(h,-1,sizeof(h));
memset(g,-1,sizeof(g));
char s[maxn];
int r,c,best=0;
scanf("%s%d%d",s,&r,&c);
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
scanf("%d",&h[i][j]);
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
best=max(dp(i,j),best);//边计算边维护最长路径,省去一次遍历。
printf("%s: %d\n",s,best+1);
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

一月最后一场,ACM-ICPC规则,没有pretest,没有hack,原本感觉会比上次简单点。。结果把自己打成绿名了。。。

一共就出了一道题。结束之后,B题改过了。

509A - Maximum in Table:

简单题,不说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn=11;
int a[maxn][maxn];
int main(){
for(int i=0;i<maxn;++i){
a[i][0]=1;
if(i==0)
for(int j=1;j<maxn;++j)
a[i][j]=1;
else
for(int j=1;j<maxn;++j)
a[i][j]=a[i-1][j]+a[i][j-1];
}
int n;
while(cin>>n)
cout<<a[n-1][n-1]<<endl;
return 0;
}

509B - Painting Pebbles:

n堆鹅卵石,用k种颜色上色,任意两堆之间的任意颜色的鹅卵石数目差要求绝对值小于1。

思路很简单,当鹅卵石数目最大值减最小值大于数目k时,则无法涂色。最少堆的鹅卵石都用1涂色。然后其他堆涂相同数目的1,剩下的递增一个颜色涂一个。

一开始没注意到可以不用到所有颜色,后来删掉k>maxp之后,忘记修改输出,一直到比赛结束没看出来,我也是神了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=110;
int a[maxn];
int main(){
int n,k;
scanf("%d%d",&n,&k);
memset(a,0,sizeof(a));
scanf("%d",&a[0]);
int maxp=a[0],minp=a[0];
for(int i=1;i<n;++i){
scanf("%d",&a[i]);
maxp=max(maxp,a[i]);
minp=min(minp,a[i]);
}
if(maxp-minp>k) printf("NO\n");
else{
printf("YES\n");
for(int i=0;i<n;++i){
bool p=1;
for(int j=0;j<minp;++j){
if(p) p=0;
else printf(" ");
printf("1");
}
for(int j=0;j<a[i]-minp;++j){
if(p) p=0;
else printf(" ");
printf("%d",j+1);
}
printf("\n");
}
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

给出背包大小n,两种宝物的体积s1、s2,两种宝物的价值v1、v2。求能装下的最大价值。

首先进行预处理,使n/s1的值尽可能小,满足O(n)的时间不超时。s2的宝物1与s1个宝物2体积相同,所以s=s1s2的体积只会拿宝物s1或s2中的一种( 当s2v1>s1*v2时,只拿宝物1,反之亦然),这样就把n转化为n%s。然后为了使n/s1尽量小,当s1<s2时,交换s1、s2和v1、v2的值。

然后从零开始枚举需要拿的v1的个数,上限是n/s1,因为进行过预处理,所以保证不会超时。求出与处理之后的最大价值。

最后加上预处理拿到的价值x就是所求答案。

还要注意一点就是,s1、s2、v1、v2的值在int范围内,但相乘之后可能溢出,所以要使用long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int k,t=0;
scanf("%d",&k);
while(k--){
long long n,s1,s2,v1,v2,x,best=0;
scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);
long long s=s1*s2,v=max(s2*v1,s1*v2);//求s=s1*s2时的最大价值v。
x=n/s*v;//预处理获得的价值。
n%=s;
if(s1<s2) swap(s1,s2),swap(v1,v2);
for(long long i=0;i<=n/s1;++i){
long long cur=0,m=n;
cur+=i*v1;
m-=i*s1;
cur+=m/s2*v2;
best=max(best,cur);//枚举维护最大价值。
}
best+=x;//二者相加。
printf("Case #%d: %lld\n",++t,best);
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

清理电脑文件找到了圣诞时比赛的代码,就来写写。

比赛一共出了两道水题,第三道坑了好久,但总体来说还是可以的,第三道题虽然没有Ac,但是它确实对了,编译器差异。。

当时的题挂在学校OJ(http://219.218.128.149/JudgeOnline/)上了1628-1632。

Problem A:

一开始没考虑<0的情况,改了之后对了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
long long l=0,k;
while(m--){
cin>>k;
l+=n-k;
}
cout<<(n-l>0?n-l:0)<<endl;
}
return 0;
}

Problem B:

简单几何。

1
2
3
4
5
6
7
8
9
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
double R,r;
while(cin>>r>>R)
printf("%.2lf %.2lf\n",(R-r)/r,(R+r)/r);
return 0;
}

Problem C:

排列组合,求概率。不是很难,但是杭电貌似不认%Lf,比赛时没出。。

学校OJ上改成%lf过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
double n,m,x,y,p,p0;
double get_p(double i0){
double k=1.0,i=i0;
int l=i0;
k*=pow(p,i0);
if(i>n-i) i=n-i;
for(int j=n;l>0;--j,--l)
k*=j,k/=l;
k*=pow(1.0-p,n-i0);
return k;
}
int main(){
while(cin>>n>>m>>x>>y>>p){
p0=0.0;
for(int i=0;i<=n;++i){
if(i*x-(n-i)*y>m) p0+=get_p((double)i);
}
printf("%.2lf\n",p0);
}
return 0;
}

Problem D:

也是排列组合,求全排列。比赛时没去做,但那一阵子正好在看紫书第十章,于是后来就把这道题做了做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<vector>
using namespace std;
const int mod=1000000007;
const int maxn=1010;
vector<int> num;
long long modn[maxn]={1};
int search(int k){
int top=(int)num.size()-1,bott=0,mid=0;
while(top>=bott){
mid=bott+(top-bott)/2;
if(k==num[mid]) return mid;
if(k>num[mid]) bott=mid+1;
else top=mid-1;
}
return mid;
}
int main(){
for(int i=1;i<maxn;i++)
modn[i]=modn[i-1]*i%mod;
int n,k;
while(cin>>n){
long long sum=1;
for(int i=1;i<=n;i++)
num.push_back(i);
for(int i=1;i<=n;i++){
cin>>k;
int p=search(k);
sum+=modn[n-i]*p%mod;
sum%=mod;
num.erase(num.begin()+p);
}
cout<<sum<<endl;
}
return 0;
}

Problem E:

当时写了超时,至今没有再去做。不过比赛结束后学长提示过用vector存路径之后暴搜。。

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

学长让去做CF的题,就把前几天的那场做了两道。

508A - Pasha and Pixels:

给出nm的像素,每次选一块,变成黑色,判断有没有出现22的黑像素,输出是第几次出现的。

思路很简单,点一个判断一次就好了。一开始用关了流同步的cin和cout,运行140ms,后来换scanf和printf,运行46ms,差了3倍多。原本以为关 掉同步之后差不了多少,没想到差这么多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<cstring>
const int maxn=1010;
bool g[maxn][maxn];
bool judge(int a,int b){
if(g[a+1][b]&&g[a][b+1]&&g[a+1][b+1]) return 1;
if(g[a+1][b]&&g[a][b-1]&&g[a+1][b-1]) return 1;
if(g[a-1][b]&&g[a][b+1]&&g[a-1][b+1]) return 1;
if(g[a-1][b]&&g[a][b-1]&&g[a-1][b-1]) return 1;
return 0;
}
int main(){
int n,m,k,i;
while(~scanf("%d%d%d",&n,&m,&k)){
memset(g,0,sizeof(g));
bool flag=1;
for(i=0;i<k;++i){
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=1;
if(flag&&judge(a,b)){
printf("%d\n",i+1);
flag=0;
}
}
if(flag) printf("0\n");
}
return 0;
}

508B - Anton and currency you all know:

输入一个奇数,输出交换两位后最大的偶数,没有的话输出-1。

单次循环,寻找最大的位置,flag标记偶数位,flag2标记能否生成偶数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[100010];
int main(){
while(~scanf("%s",s)){
int n=(int)strlen(s);
int p=0,flag=1,flag2=1;
for(int i=0;i<n;++i){
if(!(s[i]&1)){
p=i,flag2=0;
if(s[i]<s[n-1]){
swap(s[i],s[n-1]);
flag=0;
break;
}
}
}
if(flag) swap(s[p],s[n-1]);
if(flag2) printf("-1\n");
else printf("%s\n",s);
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

打完比赛一直没写,今天有时间就来写写吧。
2014年最后一场CF,不分Div.1&2。感觉挺有纪念意义所以就去机房打了。
之前只是做过CF的题,第一次去机房熬夜打比赛,有点小激动。打的成绩还可以吧,就是没想到A题有个判断写错位置被hack之后来不及改了。B、C题都Ac了。而且还 涨分了,要是A题也Ac了估计能涨很多。
500A - New Year Transportation:

单向搜索。一定要注意结束时判断的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
int n,t,flag;
while(scanf("%d%d",&n,&t)!=EOF){
flag=0;
memset(a,0,sizeof(a));
for(int i=1;i<n;++i)
scanf("%d",&a[i]);
int cur=1;
while(1){
if(cur==t){
printf("YES\n");
flag=1;
break;
}
if(cur>=n) break;
cur=cur+a[cur];
}
if(!flag) printf("NO\n");
}
return 0;
}

500B - New Year Permutation:

dfs判连通之后,每个连通的集合内部排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=310;
int a[maxn],n,cnt;
bool g[maxn][maxn];
int vis[maxn];
vector<int> num[maxn][2];
struct pos{
int a,b;
pos(int a=0,int b=0):a(a),b(b){}
bool operator < (const pos &x) const {
return b<x.b;
}
};
vector<pos> print;
void dfs(int u){
for(int v=0;v<n;++v)
if(vis[v]==-1&&g[u][v]){
vis[v]=cnt;
dfs(v);
}
return;
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(a,0,sizeof(a));
memset(g,0,sizeof(g));
memset(vis,-1,sizeof(vis));
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
getchar();
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
if(getchar()=='1') g[i][j]=g[j][i]=true;
getchar();
}
cnt=0;
for(int i=0;i<n;++i)
if(vis[i]==-1){
vis[i]=cnt;
dfs(i);
++cnt;
}
for(int i=0;i<n;++i){
num[vis[i]][0].push_back(a[i]);
num[vis[i]][1].push_back(i);
}
for(int i=0;i<cnt;++i){
sort(num[i][0].begin(),num[i][0].end());
for(int j=0;j<num[i][0].size();++j)
print.push_back(pos(num[i][0][j],num[i][1][j]));
num[i][0].clear(),num[i][1].clear();
}
sort(print.begin(),print.end());
for(int i=0;i<print.size();++i){
if(i) printf(" ");
printf("%d",print[i].a);
}
printf("\n");
print.clear();
}
return 0;
}

500C - New Year Book Reading:

模拟,看书的顺序就是堆叠的次序,有了顺序模拟搬书求总重量就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=510;
const int maxm=1010;
int n,m;
int a[maxn],b[maxm];
bool read[maxn];
vector<int> best;
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(read,0,sizeof(read));
for(int i=0;i<n;++i)
scanf("%d",&a[i]);
for(int i=0;i<m;++i){
scanf("%d",&b[i]);
if(!read[b[i]]){
best.push_back(b[i]);
read[b[i]]=true;
}
}
int sum=0;
for(int i=0;i<m;i++){
int j=0;
while(best[j]!=b[i])
sum+=a[best[j++]-1];
best.erase(best.begin()+j);
best.insert(best.begin(),b[i]);
}
printf("%d\n",sum);
best.clear();
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **

昨天统计题数错联系锟神时提到了这道题,给他讲了我的思路,感觉博客写的太简略,正好百题之后准备重新理一遍博客,所以就先来写写这道题。

有v个城市,每个城市间都有道路连通,要检查e个道路,起点终点任选。输入v、e、检查每个道路的时间t。求最少总时间。

求最少总时间,感觉与UVa818切锁链中的环有些神似。

所给的e条道路是必经的,只需要找到最少的路使得给的路形成欧拉道路即可。

首先,对所有的道路判连通,假设形成了n个连通组,那么连起来就需要n-1条路。

然后,统计每组中度数为奇数的点,每一个奇数点都要构造另一条路使之度数为偶数,但是每一组仅需形成一条链而不是环,仅需形成欧拉道路而不是欧拉回路,所以统计个数要 减去链的端点2。

最后,求每组的和,减去一就是需要连成一个整体所用的道路数,加上e,总道路就求出来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1010;
int v,e,t,cnt;
bool vis[maxn];
vector<int> g[maxn];
bool read(){
cin>>v>>e>>t;
if(!v&&!e&&!t) return false;
for(int i=0;i<maxn;++i)
g[i].clear();
memset(vis,0,sizeof(vis));
for(int i=0;i<e;++i){
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
return true;
}
void dfs(int cur){
if(vis[cur]) return;
vis[cur]=true;
cnt+=(int)g[cur].size()&1;//统计度数为奇数的点。
for(int i=0;i<g[cur].size();++i)
dfs(g[cur][i]);//DFS求连通。
return;
}
int solve(){
int ans=0;
for(int i=1;i<=v;++i){
if(!vis[i]&&!g[i].empty()){
cnt=0;
dfs(i);
ans+=max(cnt,2);//每条道路至少需要2个端点,防止出现回路出错。
}
}
return t*(max(ans/2-1,0)+e);//之前求得的和减去初始值任选可以减少的一次,再加上必经的e条道路。
}
int main(){
ios::sync_with_stdio(false);
int k=0;
while(read())
cout<<"Case "<<++k<<": "<<solve()<<endl;
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **