数据结构不难12
题目1 : 二分图一•二分图判定
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
大家好，我是小Hi和小Ho的小伙伴Nettle，从这个星期开始由我来完成我们的Weekly。
新年回家，又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表，上面都是姑姑介绍相亲的剩男剩女们。每行有2个名字，表示这两个人有一场相亲。由于姑姑年龄比较大了记性不是太好，加上相亲的人很多，所以姑姑一时也想不起来其中有些人的性别。因此她拜托我检查一下相亲表里面有没有错误的记录，即是否把两个同性安排了相亲。
OK，让我们愉快的暴力搜索吧！
才怪咧。
对于拿到的相亲情况表，我们不妨将其转化成一个图。将每一个人作为一个点(编号1..N)，若两个人之间有一场相亲，则在对应的点之间连接一条无向边。(如下图)
14238947716934.png
因为相亲总是在男女之间进行的，所以每一条边的两边对应的人总是不同性别。假设表示男性的节点染成白色，女性的节点染色黑色。对于得到的无向图来说，即每一条边的两端一定是一白一黑。如果存在一条边两端同为白色或者黑色，则表示这一条边所表示的记录有误。
由于我们并不知道每个人的性别，我们的问题就转化为判定是否存在一个合理的染色方案，使得我们所建立的无向图满足每一条边两端的顶点颜色都不相同。
那么，我们不妨将所有的点初始为未染色的状态。随机选择一个点，将其染成白色。再以它为起点，将所有相邻的点染成黑色。再以这些黑色的点为起点，将所有与其相邻未染色的点染成白色。不断重复直到整个图都染色完成。(如下图)
img2.png
在染色的过程中，我们应该怎样发现错误的记录呢？相信你一定发现了吧。对于一个已经染色的点，如果存在一个与它相邻的已染色点和它的颜色相同，那么就一定存在一条错误的记录。(如上图的4，5节点)
到此我们就得到了整个图的算法：
- 选取一个未染色的点u进行染色
- 遍历u的相邻节点v：若v未染色，则染色成与u不同的颜色，并对v重复第2步；若v已经染色，如果 u和v颜色相同，判定不可行退出遍历。
- 若所有节点均已染色，则判定可行。
接下来就动手写写吧！
输入
第1行：1个正整数T(1≤T≤10)
接下来T组数据，每组数据按照以下格式给出：
第1行：2个正整数N,M(1≤N≤10,000，1≤M≤40,000)
第2..M+1行：每行两个整数u,v表示u和v之间有一条边
输出
第1..T行：第i行表示第i组数据是否有误。如果是正确的数据输出”Correct”，否则输出”Wrong”
样例输入
2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5
样例输出
Wrong
Correct
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T;
int n, m;
const int maxn = 10005;
vector<int> G[maxn];
bool vis[maxn];
int f[maxn];
int bfs(int i) {
queue<int> que;
que.push(i);
vis[i] = true;
f[i] = 0;
while(!que.empty()) {
int e = que.front();
que.pop();
int d = G[e].size();
// cout << e << endl;
for(int i = 0; i < d; i ++) {
int t = G[e][i];
// cout << t << " ";
if(vis[t]) {
if(f[t] == f[e]) return 1;
}
else {
vis[t] = true;
f[t] = f[e] == 0 ? 1 : 0;
que.push(t);
}
}
// cout << endl;
}
return 0;
}
int fun() { //注意可能会有多个连通分量
for(int i = 1; i <= n; i ++) {
if(!vis[i]) {
if(bfs(i) == 1) return 1;
}
}
return 0;
}
int main() {
scanf("%d", &T);
while(T --) {
// for(int i = 0; i < maxn; i ++) G[i].clear();
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i ++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
memset(vis, false, sizeof(vis));
if(fun() == 1) {
printf("Wrong\n");
}
else printf("Correct\n");
// for(int i = 1; i <= n; i ++) {
// cout << f[i] << " ";
// }
for(int i = 1; i <= n; i ++) G[i].clear();
}
return 0;
}
题目2 : 树结构判定
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个包含 N 个顶点 M 条边的无向图 G ，判断 G 是不是一棵树。
输入
第一个是一个整数 T ，代表测试数据的组数。 (1 ≤ T ≤ 10)
每组测试数据第一行包含两个整数 N 和 M 。(2 ≤ N ≤ 500, 1 ≤ M ≤ 100000)
以下 M 行每行包含两个整数 a 和 b ，表示顶点 a 和顶点 b 之间有一条边。(1 ≤ a, b ≤ N)
输出
对于每组数据，输出YES或者NO表示 G 是否是一棵树。
样例输入
2
3 2
3 1
3 2
5 5
3 1
3 2
4 5
1 2
4 1
样例输出
YES
NO
AC代码
//并查集
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int ma=510;
int fa[ma];
int findfa(int x)
{
if(x==fa[x]) return x;
return fa[x]=findfa(fa[x]);
}
int main()
{
int t;
scanf("%d",&t);
int n,m;
while(t--)
{
scanf("%d%d",&n,&m);
bool fg=false;
if(m!=n-1) fg=true;
for(int i=1;i<=n;++i) fa[i]=i;
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
int fx=findfa(x),fy=findfa(y);
if(fa[fx]!=fa[fy])
fa[fx]=fa[fy];
}
if(fg)
{
printf("NO\n");
continue;
}
int root=findfa(fa[1]);
for(int i=2;i<=n;++i)
if(findfa(fa[i])!=root)
{
fg=true;
break;
}
if(fg) printf("NO\n");
else printf("YES\n");
}
return 0;
}
题目3 : 最小生成树二·Kruscal算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
随着小Hi拥有城市数目的增加，在之间所使用的Prim算法已经无法继续使用了——但是幸运的是，经过计算机的分析，小Hi已经筛选出了一些比较适合建造道路的路线，这个数量并没有特别的大。
所以问题变成了——小Hi现在手上拥有N座城市，且已知其中一些城市间建造道路的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
提示：积累的好处在于可以可以随时从自己的知识库中提取想要的！
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为2个整数N、M，表示小Hi拥有的城市数量和小Hi筛选出路线的条数。
接下来的M行，每行描述一条路线，其中第i行为3个整数N1_i, N2_i, V_i，分别表示这条路线的两个端点和在这条路线上建造道路的费用。
对于100%的数据，满足N<=10^5, M<=10^6，于任意i满足1<=N1_i, N2_i<=N, N1_i≠N2_i, 1<=V_i<=10^3.
对于100%的数据，满足一定存在一种方案，使得任意两座城市都可以互相到达。
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
样例输入
5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185
样例输出
92
AC代码
#include<stdio.h>
struct edge
{
int u;
int v;
int w;
};
struct edge e[1000010];
int n,m;
int f[100010]={0},sum=0,count=0;
void quicksort(int left,int right)
{
int i,j;
struct edge t;
if(left>right)
return;
i=left;
j=right;
while(i!=j)
{
while(e[j].w>=e[left].w&&i<j)
j--;
while(e[i].w<=e[left].w&&i<j)
i++;
if(i<j)
{
t=e[i];
e[i]=e[j];
e[j]=t;
}
}
t=e[left];
e[left]=e[i];
e[i]=t;
quicksort(left,i-1);
quicksort(i+1,right);
return;
}
int getf(int v)
{
if(f[v]==v)
return v;
else
{
f[v]=getf(f[v]);
return f[v];
}
}
int merge(int v,int u)
{
int t1,t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2)
{
f[t2]=t1;
return 1;
}
return 0;
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
quicksort(1,m);
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
{
if(merge(e[i].u,e[i].v))
{
count++;
sum+=e[i].w;
}
if(count==n-1)
break;
}
printf("%d\n",sum);
return 0;
}
题目4 : 最小生成树一·Prim算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条道路连通的）。
提示：不知道为什么Prim算法和Dijstra算法很像呢Σ(っ °Д °;)っ 。
输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
样例输入
5
0 1005 6963 392 1182
1005 0 1599 4213 1451
6963 1599 0 9780 2789
392 4213 9780 0 5236
1182 1451 2789 5236 0
样例输出
4178
AC代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf=1e9;
const int maxn=1010;
int dis[maxn],ans;
int a[maxn][maxn];
int used[maxn],n;
void _prim()
{
int i,j,Min,pos;
for(i=1;i<=n;i++) dis[i]=inf;
dis[1]=0;
//_prim();
for(i=1;i<=n;i++){
Min=1e9;
for(j=1;j<=n;j++){
if(!used[j]&&dis[j]<Min){
Min=dis[j];pos=j;
}
}
used[pos]=1;
ans+=dis[pos];
for(j=1;j<=n;j++)
if(dis[j]>a[pos][j])
dis[j]=a[pos][j];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
_prim();
printf("%d\n",ans);
return 0;
}
