**构造无向图欧拉道路的一道题。
欧拉道路存在的条件:1、最多只能有两个度数为奇数的结点 2、图是连通的
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1001;
vector<int>G[maxn];
int v,e,t;
int res[maxn];
int dfs(int u)
{
int cnt=0;
res[u]=0;
int n=G[u].size();
if(n%2) ++cnt;
for(int i=0;i<n;i++)
{
if(res[G[u][i]])
cnt+=dfs(G[u][i]);
}
return cnt;
}
int solve()
{
int ans=0;
for(int i=1;i<=v;i++)
{
if(res[i])
ans+=(dfs(i)-1)/2+1;
}
return max(ans-1,0);
}
int main(void)
{
int num=0;
while(scanf("%d%d%d",&v,&e,&t)==3&&v!=0)
{
int ans=0;
memset(res,0,sizeof(res));
int x,y;
for(int i=0;i<e;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
res[x]=1;res[y]=1;
++ans;
}
//printf("%d %d\n",ans,solve());
printf("Case %d: %d\n",++num,t*(ans+solve()));
for(int i=1;i<=v;++i)
G[i].clear();
}
return 0;
}
所有评论(0)