# 4.3算法之图论 1526:宗教信仰 并查集模板题

http://noi.openjudge.cn/ch0403/1526/

#### 源码

``````//
//  1526.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> father;

int find(int x){
return x==father[x]?x:find(father[x]);
}
void un(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx>fy){
father[fy]=fx;
}else{
father[fx]=fy;
}
}
int main(){
int m,n;
int idx=0;
while(cin>>n>>m){
idx++;
if(n==0&&m==0)break;
father.clear();
for(int i = 0;i <=n;++i){
father.push_back(i);
}
while(m--){
int a,b;
cin >> a>>b;
un(a,b);
}
int res = 0;
for(int i = 1;i <=n;++i){
if(find(i)==i){
res++;
}
}
cout<<"Case "<< idx<<": "<<res<<endl;
}
return 0;
}

``````

# 4.3算法之图论 1538:Gopher II 匈牙利算法

http://noi.openjudge.cn/ch0403/1538/

#### 源码

``````//
//  1538.cpp
//  test
//
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int n,m,s,v;

struct Node{
float x,y;
Node(float x,float y):x(x),y(y){}
};
bool isE(Node &a,Node &b){
float dis = pow(a.x-b.x,2)+pow(a.y-b.y,2);
return dis-1.0*s*s*v*v<1e-6;
}

vector<Node> nodesA;
vector<Node> nodesB;
vector<bool> vis;//本次找增广路使
vector<int> to;//记录匹配节点
bool dfs(int x){
for(int i = 1;i <= m;++i){
if(!vis[i]&&isE(nodesB[i],nodesA[x])){
vis[i]=true;
if(to[i]==0||dfs(to[i])){
to[i]=x;
return true;
}
}
}
return false;
}

int main(){
while(cin >> n >> m){
cin >>s>>v;
to.clear();
nodesA.clear();
nodesB.clear();
vis.resize(m+1,false);
to.resize(m+1,0);
nodesA.push_back(Node(-1,-1));
nodesB.push_back(Node(-1,-1));
for(int i = 0;i < n;++i){
float x,y;
cin >> x>>y;
nodesA.push_back(Node(x,y));
}
for(int i = 0;i < m;++i){
float x,y;
cin >> x>>y;
nodesB.push_back(Node(x,y));
}
//dfs二分图匹配
int res = 0;
for(int i = 1;i <= n;++i){
vis.clear();
vis.resize(m+1,false);
if(dfs(i)){
//cout<<"zgl "<<i<<endl;
res++;
}
}
cout <<n-res<<endl;
}
return 0;
}

``````

# 4.3算法之图论 253:丛林中的路

http://noi.openjudge.cn/ch0403/253

#### 思路

kruskal，边集按照 cost 排序遍历，并查集检查连通性，如果边的两端不连通则加入集合，放进集合

##### 源码
``````//
//  253.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

struct Edge{
int st,ed,cost;
Edge(int st,int ed,int cost):st(st),ed(ed),cost(cost){}
bool operator < (const Edge & e) const{
return cost<e.cost;
}
};
using namespace std;
int find(vector<int>& father,int x){
return father[x]==x?x:find(father,father[x]);
}
void un(int x,int y,vector<int> & father){
int fx = find(father,x);
int fy = find(father,y);
if(fx>fy){
father[fy]=fx;
}else{
father[fx]=fy;
}
}
int main(){
int num;
while(cin>>num){
// cout <<"num"<< num<<endl;
if(num==0)break;
vector<int> father(num);
for(int i = 0;i < num;++i)father[i] = i;
vector<Edge> edges;
char stchar;
num--;
while(num--){
cin >> stchar;
int edgenum;
cin >> edgenum;
while(edgenum--){
char edchar;
int cost;
cin >> edchar>>cost;
edges.push_back(Edge(stchar-'A',edchar-'A',cost));
}
}
sort(edges.begin(),edges.end());
//kruskal
int res = 0;
for(int i = 0;i < edges.size();++i){
//cout <<"cost"<< edges[i].cost<<endl;
int st = edges[i].st;
int ed = edges[i].ed;
if(find(father,st)!=find(father,ed)){
res+=edges[i].cost;
un(st,ed,father);
}
}
cout << res<<endl;

}
return 0;
}

``````

http://noi.openjudge.cn/ch0403/726/

#### 源码

``````//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <algorithm>
#define INT_MAX 999999999
using namespace std;
int k,n,r;
int to,d,c;
bool operator < (const Road &r) const {
if(d==r.d)return c<r.c;
return d > r.d;
}
};
vector<vector<bool>> vis;
vector<int> dis;

int main(){
cin >> k >> n >> r;
dis.resize(n+1,INT_MAX);
vis.resize(n+1,vector<bool>(n+1,false));
for(int i = 0;i < r;++i){
int a,b,c,d;
cin >> a>>b>>c>>d;
}

while(!q.empty()){
q.pop();
return 0;
}
for(int j = 0;j < edge[internal].size();++j){
}
}
}

return 0;
}

``````

# 4.3算法之图论 799 Heavy Transportation

http://noi.openjudge.cn/ch0403/799/

-1代表路径不通

#### AC源码

``````//
//  799.cpp
//  test
//
//  Created by bytedance on 2020/7/15.
//

#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#define INT_MAX 999999
#define close -1
using namespace std;

struct Node{
int d,u;
Node(int d,int u):d(d),u(u){}
bool operator <(const Node & a) const{
return d<a.d;
}
};
int main(){
int n;
cin >> n;
int vs,es;

for(int i = 1;i <= n;++i){
cin >> vs >> es;
vector<vector<int>> e(vs+1,vector<int>(vs+1,-1));
vector<bool> vis(vs+1,false);
vector<int> dis(vs+1,-1);
while(es--){
int a,b,c;
cin >> a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
//dijkstra

priority_queue<Node> q;
q.push(Node(-1,1));
dis[1] = INT_MAX;
while(!q.empty()){
Node t = q.top();
q.pop();
int d = t.d;
int u = t.u;
//cout << d<<endl;
if(vis[u])continue;
vis[u]=true;
for(int j = 1;j <= vs; ++j){
if(!vis[j]&&dis[j]<min(dis[u],e[u][j])){
dis[j]=min(dis[u],e[u][j]);
q.push(Node(dis[j],j));
}
}
}
cout <<"Scenario #"<<i<<":"<<endl<<dis[vs]<<endl<<endl;
}
return 0;
}

``````