挑战程序设计竞赛-day9

温习一下Floyd算法

POJ 2139： Six Degrees of Cowvin Bacon

大意：

牛去拍电影，在同一场表演的牛的距离为1，牛与牛之间的距离可以是间接的，例如a和b拍一场，b和c拍一场，a和c之间没在同一场拍，则a和c的距离为2，求牛与其他牛的距离最小平均值，自己和自己距离为0。最小的平局值乘一百输出。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
typedef long long ll;
const int MAXN = 305;
const int MAXM = 10010;
int matrix[MAXN][MAXN];
int movie[MAXM];
int n, m;
void solve() {
    ll res = INT_MAX;
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(matrix[i][k] >= 0 && matrix[k][j] >= 0 && ((matrix[i][k] + matrix[k][j] < matrix[i][j]) || (matrix[i][j] < 0))) {
                    matrix[i][j] = matrix[i][k] + matrix[k][j];
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        ll sum = 0;
        for(int j = 1; j <= n; j++) {
            sum += matrix[i][j];
        }
        res = min(res, 100 * sum / (n - 1));
    }
    printf("%lld\n", res);
}

void read() {
    memset(matrix, -1, sizeof(matrix));
    for(int i = 0; i <= n; i++) {
        matrix[i][i] = 0;
    } 
    for(int i = 0; i < m; i++) {
        memset(movie, 0, sizeof(movie));
        int num;
        scanf("%d", &num);
        for(int j = 0; j < num; j++) {
            scanf("%d", &movie[j]);
        }
        for(int j = 0; j < num; j++) {
            for(int k = j + 1; k < num; k++) {
                matrix[movie[j]][movie[k]] = 1;
                matrix[movie[k]][movie[j]] = 1;
            }
        }
    }
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        read();
        solve();
    }
}

Floyd

// k是枚举中间经过的点
for(int k = 1; k <= G.n; k++) {
    for(int i = 1; i <= G.n; i++) {
        for(int j = 1; j <= G.n; j++) {
            map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
        }
    }
}

POJ 3259： Warmholes

大意：

农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1…N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。作为一个狂热的时间旅行FJ的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的映射到（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都不大于万秒的时间回溯。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 505;
const int INF = 0x3f3f3f3f;
int n, m, k, num = 0;
int matrix[MAXN][MAXN];

void floyd() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                int t = matrix[i][k] + matrix[k][j];
                if(matrix[i][j] > t) {
                    matrix[i][j] = t;
                }
            }
            if(matrix[i][i] < 0) {
                printf("YES\n");
                return ;
            }
        }
    }
    printf("NO\n");
    return ;
}

int main() {
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        scanf("%d%d%d", &n, &m, &k);
        int a, b, c;
        memset(matrix, INF, sizeof(matrix));
        for(int i = 1; i <= n; i++) {
            matrix[i][i] = 0;
        }
        for(int i = 1; i <= m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            if(c < matrix[a][b]) {
                matrix[a][b] = matrix[b][a] = c;
            }
        }
        for(int i = 1; i <= k; i++) {
            scanf("%d%d%d", &a, &b, &c);
            matrix[a][b] = -c;
        }
        floyd();

    }
}

负环（SPFA）

http://www.sohu.com/a/244179200_100201031

const int INF = 0x3f3f3f3f;

int dis[MAXN];  // dis[i]=源点s->i最短路径
bool vis[MAXN]; // vis[i]表示i是否在队列

// bfs
void spfa(int s) {
    // 初始化
    memset(dis, INF, sizeof(dis));
    memset(vis, 1, sizeof(vis));

    dis[s] = 0;
    queue<int> q;
    q.push(s);
    vis[s] = false;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        // 
        for(int i = head[u]; !i; i = ed[i].next) {
            int v = ed[i].to;
            // 如果不满足三角不等式 
            if(dis[u] + ed[i].w < dis[v]) {
                dis[v] = dis[u] + ed[i].w;
                // 如果终点不在队列
                if(vis[v]) {
                    q.push(v);
                    vis[v] = false;
                }
            }
        }
    }
}

// dfs
void spfa(int a) {
    instack[a] = true;      // 节点入栈
    for(int i = head[a]; ~i; i = Ed[i].next) {  // 遍历出边
        if(dis[a] + Ed[i].w < dis[Ed[i].to]) {  
            dis[Ed[i].to] = dis[a] + Ed[i].w;   // 更新答案
            if(!instack[Ed[i].to]) {        // 如果重点不在栈内
                spfa(Ed[i].to); // 深搜
            } else {
                return ;    // 有负环
            }
        }
    }
    instack[a] = false;
}

Dijkstra算法 + 堆优化

#include <cstdio>
#include <queue>
#include <vector>
#define MAXN 200010
#define INF 0x3fffffff
using namespace std;
struct edge{
    int v,w;
    edge(int v, int w):v(v),w(w){}
};
vector <edge> mp[MAXN];
int dis[MAXN];
bool vis[MAXN];
int n,m,s;
struct node{
    int v,dis;
    node(int v, int dis):v(v),dis(dis){}
    const bool operator < (const node &a) const{
        return a.dis < dis;
    }
};
priority_queue <node> q;

void dj(){
    for(register int i=1;i<=n;i++)
        dis[i]=INF;
    dis[s]=0;
    q.push(node(s, 0));
    while(!q.empty()){
        node cur = q.top();
        q.pop();
        if(vis[cur.v])  continue;
        vis[cur.v] = 1;
        for(register int i=0;i<mp[cur.v].size();i++){
            edge to = mp[cur.v][i];
            if(vis[to.v]) continue;
            if(dis[to.v]>to.w+dis[cur.v]){
                dis[to.v]=to.w+dis[cur.v], q.push(node(to.v, dis[to.v]));
            }
        }
    }
    for(register int i=1;i<=n;i++)
        printf("%d ", dis[i]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(register int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d", &u, &v, &w);
        mp[u].push_back(edge(v, w));
    }
    dj();
    return 0;
}