최소 트 리 이분 도 템 플 릿 생 성

최소 생 성 트 리 (정 변, 마이너스 모두 가능)
Prim 소박 판 O (n ^ 2)

조밀도, 코드 가 짧 고 Dij 와 비슷 하 다

알고리즘 프로 세 스 (점 으로 확장): dist [i] 를 무한 으로 초기 화 합 니 다.
for i 0 ~ n
우선 외부 거리 에서 가장 가 까 운 점 할당 t 를 집합 합 니 다.
t 로 다른 점 에서 집합 까지 의 거 리 를 업데이트 합 니 다.
​ st[t] = true;
* 그 중에서 점 에서 집합 까지 의 거 리 는 집합 외 점, 집합 내 점 까지 의 거리, 가장 작은 쪽 으로 정의 합 니 다.

#include 
#include 
#include 
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int g[N][N],dist[N],n,m;
bool st[N];
int prim(){
    int ret = 0;
    memset(dist,0x3f,sizeof dist);
    for(int i = 0;i < n; ++i){
        int t = -1;
        for(int j = 1;j <= n; ++j){ //        ，           
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[t] = 1;
        if(i && dist[t] == INF) return -1; //             INF，     ，     
        //               
        if(i) ret += dist[t];//      ，      ，dist t       
        //    ，   ，（            ，     1-1 ，    -10）
        for(int j = 1;j <= n; ++j) dist[j] = min(dist[j],g[t][j]); //    t           
        //   for     ，               t      ，j       
    }
    return ret; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int u,v,w;
    cin >> n >> m;
    for(int i = 0;i <= n; ++i) 
        for(int j = 0;j <= n; ++j)
            g[i][j] = g[j][i] = INF;
    while(m--){
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v],w);
    }
    int ans = prim();
    cout << ans ;
    return 0;
}

Kruskal O(mlogm)

희소 도

알고리즘 프로 세 스 (변 으로 확장 하고 집합 하 는 사상)

모든 변 을 가중치 에 따라 작은 것 부터 큰 것 까지 정렬 (sort)

매 변 a - > b, 가중치 c

a 와 b 가 연결 되 지 않 으 면 a - > b 이 변 을 집합 에 넣 습 니 다

#include 
#include 
#include 
using namespace std;
const int M = 2e5 + 10,N = 1e5 + 10;
int p[N],n,m;
struct Edge{
    int a,b,w;
    bool operator < (const Edge & W) const{
        return w < W.w;
    }
}edges[M];
int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int cnt = 0,ret = 0;
    cin >> n >> m;
    for(int i = 0;i < m; ++i){
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    sort(edges,edges + m);
    for(int i = 1;i <= n; ++i) p[i] = i;
    for(int i = 0;i < m; ++i){
        int a = edges[i].a,b = edges[i].b,w = edges[i].w;
        a = find(a),b = find(b);
        if(a != b){
            p[a] = b;
            ret += w;
            cnt ++;
        }
    }
    if(cnt < n-1) cout << "impossible";
    else cout << ret ;
    return 0;
}

이분 도
염색법 (DFS 로 이분 도 판정) O (m + n)
성질:

한 그림 은 2 분 의 그림 이 고 그림 에 만 홀수 링 이 포함 되 어 있 지 않다. 한 점 에서 출발 하여 다시 출발점 으로 돌아 가 는 경로 홀수 링: 링 의 수량 은 홀수

이다.

so. 만약 에 한 그림 에 홀수 고리 가 있다 면 이것 은 이분 도 증명 이 아 닐 것 이다. 고리 중의 첫 번 째 점 은 왼쪽 에 있 고 두 번 째 점 은 반드시 오른쪽 에 있 을 것 이다.순서대로 유추 하면 링 이 홀수 라면 우 리 는 내 놓 을 수 있 고 출발점 은 오른쪽 에 속 하 며 이미 알 고 있 는 것 과 모순 된다.

알고리즘 흐름:

for i 1 ~ n

i 가 dfs (i) 를 염색 하지 않 으 면 i 가 있 는 연결 블록 을 모두 염색 합 니 다

#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],w[N],h[N],idx,n,m;
int color[N];
void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
bool dfs(int u,int c){
    color[u] = c;
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(!color[j]){
            if(!dfs(j,3-c)) return 0;
        }
        else if(color[j] == c) return 0;
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);
    int a,b,c;
    cin >> n >> m;
    for(int i = 0;i < m; ++i){
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    bool f = 1;
    for(int i = 1;i <= n; ++i){
        if(!color[i] && !dfs(i,1)){
            f = 0;
            break;
        }
    }
    if(f) cout << "Yes";
    else cout <

헝가리 알고리즘 (최대 일치 요구) O (m + n) 의 실제 운행 시간 은 O (mn) 보다 훨씬 적다.
알고리즘 흐름:

for i 1 ~ n 남자 한 명 씩 보기 (왼쪽 점)

먼저 모든 여동생 의 태그 st 를 비 웁 니 다 (오른쪽 에 있 는 태그 점 집합 상황)

find (i) 가 진짜 로 돌아 오 면 res +

find（x）

이 남자 가 마음 에 드 는 여자 j 를 매 거 한다.

현재 여동생 이 뽑 히 지 않 았 다 면

현재 여동생 종이 태그 가 선택 되 었 습 니 다

현재 여동생 종이 가 남자 와 일치 하지 않 거나 해당 여동생 이 일치 하 는 남자 가 다음 집 을 찾 을 수 있다 면 (이렇게 여동생 종이 가 비어 있다)

일치 하 는 배열 match [j] = i 를 표시 합 니 다.

마지막 에 못 찾 으 면 false

로 돌아 갑 니 다.

#include 
#include 
using namespace std;
const int N = 510,M = 1e5 + 10;
int n1,n2,m;
int h[N],e[M],ne[M],idx,match[N];
bool st[N];
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
bool find(int x){
    for(int i = h[x];i != -1;i = ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = 1;
            if(match[j] == 0 || find(match[j])){
                match[j] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int u,v,res = 0;
    cin >> n1 >> n2 >> m;
    memset(h,-1,sizeof h);
    while(m--){
        cin >> u >> v;
        add(u,v);
    }
    for(int i = 1;i <= n1; ++i){
        memset(st,0,sizeof st);
        if(find(i)) res ++;
    }
    cout << res;
    return 0;
}