信息奥赛题解目录T（部分答案）

本文主要是介绍信息奥赛题解目录T（部分答案），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

信息奥赛题解目录T（部分答案）

1.3.4 图论

T1341 - 一笔画问题

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
using namespace std;bool g[1010][1010];
int c[1000010];
int n, m;int pos = 0;
int a[1000010];void dfs(int x)
{for(int i = 1; i <= n; i ++){if(g[x][i] == true){g[x][i] = g[i][x] = false;dfs(i);}}a[++ pos] = x;
}void print(int x)
{if(x == pos + 1){return ;}printf("%d ", a[x]);print(x + 1);
}int main()
{scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++){int x, y;scanf("%d%d", &x, &y);g[x][y] = g[y][x] = true;c[x] ++;c[y] ++;}int AC = 1;for(int i = 1; i <= n; i ++){if(c[i] % 2 == 1){AC = i;break;}}dfs(AC);print(1);return 0;
}

T1391 - 局域网(net)

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[100010];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);
}struct Edge{int a,b,c;bool operator<(const Edge&cmp2){return c<cmp2.c;}
}edge[100010];int main(){int n,m,sum=0,ret=0;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);sum+=c;edge[i].a=a;edge[i].b=b;edge[i].c=c;}for(int i=1;i<=n;i++)fa[i]=i;sort(edge+1,edge+m+1);for(int i=1;i<=m;i++){int a=edge[i].a,b=edge[i].b,c=edge[i].c;int ta=find(a),tb=find(b);if(ta!=tb){fa[ta]=tb;ret+=c;} }printf("%d\n",sum-ret);return 0;
}

这篇关于信息奥赛题解目录T（部分答案）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---