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

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

思路

并查集模板题

源码

//
//  1526.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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;
}

4.3算法之图论 726:ROADS

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

思路

狄杰斯特拉直接改一下,基于优先级队列
Road 设置为二关键字排序
优先级队列 push 时只 push cost 小于等于 k 的 Road,则队列头部 Road.to 为 n 时必为满足 k 的最短路

源码

//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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;
struct Road{
    int to,d,c;
    Road(int to,int d,int c):to(to),d(d),c(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;
vector<vector<Road>> edge;


int main(){
    cin >> k >> n >> r;
    edge.resize(n+1,vector<Road>());
    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;
        edge[a].push_back(Road(b,c,d));
    }

    priority_queue<Road> q;
    q.push(Road(1,0,0));
    while(!q.empty()){
        Road road = q.top();
        q.pop();
        if(road.to==n){
            cout <<road.d;
            return 0;
        }
        int internal = road.to;
        for(int j = 0;j < edge[internal].size();++j){
            int des = edge[road.to][j].to;
            if(k>=road.c+edge[road.to][j].c){
                q.push(Road(des,road.d+edge[road.to][j].d,road.c+edge[road.to][j].c));
            }
        }
    }

    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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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;
}