读书笔记

/**
给定一个具有n个顶点的图。要给图上每个顶点染色，并且要让相邻的定点颜色不同。
问能否只用两种颜色完成。
规模：
1 <= n <= 1000
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
const int N = 1000 + 5;

int n, m;
vector<int> G[N];
int color[N];

int dfs(int v, int c)
{
    color[v] = c;
    for(int i = 0; i < G[v].size(); i++)
    {
        if(color[G[v][i]] == c) //颜色相同不能染
            return 0;
        if(color[G[v][i]] == 0 && !dfs(G[v][i], -c)) //当前可以染色，但是以后会失败
            return 0;
    }
    return 1;
}

void read()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

void solve()
{
    read();
    for(int i = 0; i < n; i++)
    {
        if(color[i] == 0)
        {
            if(!dfs(i, 1))
            {
                printf("No
");
                return;
            }
        }
    }
    printf("Yes
");
}

int main()
{
    solve();
    return 0;
}

/**
哈哈，终于到模板问题了。
最短路算法的核心之处就是一个状态转移
d[i] = min(d[i], d[j] + length(j,i))
Bellman-Ford算法一个以考虑边来优化的算法
就是不断遍历所有的边，如果可以优化d[],那么就优化。
直到有一次遍历所有边都没有办法优化了为止
复杂度O(NE)。
使用FIFO队列，最坏O(NE)
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
const int N = 20000 + 5;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int u;
    int v;
    int w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
};

vector<int> G[N];
vector<Edge> edge;
int n, m;
int inque[N];
int d[N];
int cnt[N];
int pre[N];

void init()
{
    for(int i = 0; i < N; i++)
        G[i].clear();
    edge.clear();
}

void read()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge.push_back(Edge(u, v, w));
        G[u].push_back(edge.size() - 1);
    }
}

bool Bellman_Ford(int s)
{
    memset(inque, 0, sizeof(inque));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++)
        d[i] = INF;
    queue<int>  Q;
    while(Q.size()) Q.pop();
    Q.push(s);
    d[s] = 0;
    inque[s] = 1;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop(); inque[u] = 0;
        for(int i = 0; i < G[u].size(); i++)
        {
            Edge &e = edge[G[u][i]];
            if(d[e.v] > d[e.u] + e.w)
            {
                d[e.v] = d[e.u] + e.w;
                pre[e.v] = pre[e.u];
                if(!inque[e.v])
                {
                    Q.push(e.v);
                    inque[e.v] = 1;
                    cnt[e.v]++;
                    if(cnt[e.v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    init();
    read();
    if(!Bellman_Ford(0))
    {
        printf("Negative Circle
");
        return 0;
    }
    for(int i = 0; i < n; i++)
        printf("%d
", d[i]);
    return 0;
}

/**
带堆优化的Dijstra算法，复杂度最坏O(n^2)，比BELLMAN-FORD稳定
模板算法
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> P;
const int N = 20000 + 5;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int u;
    int v;
    int w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
};

vector<int> G[N];
vector<Edge> edge;
int n, m;
int d[N];
int pre[N];

void init()
{
    for(int i = 0; i < N; i++)
        G[i].clear();
    edge.clear();
}

void read()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge.push_back(Edge(u, v, w));
        G[u].push_back(edge.size() - 1);
    }
}

void Dijkstra(int s)
{
    for(int i = 0; i < n; i++)
        d[i] = INF;
    d[s] = 0;
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(d[s], s));

    while(!pq.empty())
    {
        P t = pq.top(); pq.pop();
        int u = t.second;
        if(d[u] < t.first) continue;
        for(int i = 0; i < G[u].size(); i++)
        {
            Edge &e = edge[G[u][i]];
            if(d[e.v] > d[e.u] + e.w)
            {
                d[e.v] = d[e.u] + e.w;
                pre[e.v] = e.u;
                pq.push(P(d[e.v], e.v));
            }
        }
    }
}

int main()
{
    init();
    read();
    Dijkstra(0);
    for(int i = 1; i < n; i++)
        printf("%d
", d[i]);
    return 0;
}

/**
Floyd算法
5行
所有的最短路，O(N^3)
传递闭包
适应于规模很小的题，但很有用
**/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 500 + 5;
int d[N][N];
int n;

void Floyd()
{
    memset(d, 0x3f, sizeof(d));
    for(int k = 0; k < n; k++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(d[i][j] <= INF && d[i][j] > d[i][k] + d[k][j])
                {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main()
{
    Floyd();

    //To do

    return 0;
}