poj-1860

题目大意

有多个兑换点, 每个兑换点可以兑换两种货币. 假设本来有的货币种类为s, 问能否通过不断兑换最终回到s并且使总金增加

理解

  • 如果存在正权回路则说明可以钱无限增加, 找到正权回路直接输出YES就行了, 否则输出NO

code

/**********************************************************
    > File Name : poj-1860.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 24 15:43:13
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
struct poin{
    int a, b;
    double r, c;
}expp[220];
// 刚开始定义的是exp[220], 不知道这是个关键字, 报错了

int nume;
int n, m, s;
double v;
// 到第[]种货币的最大值
double dis[101];
bool bell(){
    memset(dis, 0, sizeof(dis));
    dis[s] = v;
    for(int i = 0; i < n - 1; i++){
        bool flag = false;
        for(int j = 0; j < nume; j++){
            if(dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r){
                dis[expp[j].b] = (dis[expp[j].a] - expp[j].c) * expp[j].r;
                flag = true;
            }
        }
        if(!flag) break;
    }
    for (int j = 0; j < nume; j++) {
        if (dis[expp[j].b] < (dis[expp[j].a] - expp[j].c) * expp[j].r) {
            return true;
        }
    }
    return false;
}
int main(){
    while(cin >> n >> m >> s >> v){
        nume = 0;
        int exa, exb;
        double exra, exca, exrb, excb;
        for(int i = 0; i < m; i++){
            scanf("%d %d %lf %lf %lf %lf", &exa, &exb, &exra, &exca, &exrb, &excb);
            expp[nume].a = exa;
            expp[nume].b = exb;
            expp[nume].r = exra;
            expp[nume++].c = exca;
            expp[nume].a = exb;
            expp[nume].b = exa;
            expp[nume].r = exrb;
            expp[nume++].c = excb;
        }
        if(bell()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

poj-3295

题目大意

有f个农场, 每个农场有n个点m条路, 有w个虫洞, 问针对每个农场能否看到以前的自己

理解

  • 判断是否有负权回路, 有就可以

code

/**********************************************************
    > File Name : poj-3295.cpp
    > Author : Wqr_
    > Mail : xueduanwei@126.com
    > Created Time : 19 03 24 17:15:01
**********************************************************/
#include <iostream>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
#define INF 1<<28
using namespace std;
int n, m, w;
int eee;
struct edge{
    int a, b, cost;
}es[10010];

int dis[10010];

bool bell(){
    fill(dis, dis + n, INF);
    dis[1] = 0;
    for(int i = 0; i < n - 1; i++){
        bool flag = false;
        for(int j = 0; j < eee; j++){
            if(dis[es[j].b] > dis[es[j].a] + es[j].cost){
                dis[es[j].b] = dis[es[j].a] + es[j].cost;
                flag = true;
            }
        }
        if(!flag) break;
    }
    for (int j = 0; j < eee; j++) {
        if (dis[es[j].b] > dis[es[j].a] + es[j].cost) {
            return true;
        }
    }
    return false;
}
int main(){
    int f;
    cin >> f;
    while(f--){
        eee = 0;
        cin >> n >> m >> w;
        int a, b, c;
        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &a, &b, &c);
            es[eee].a = a;
            es[eee].b = b;
            es[eee++].cost = c;
            es[eee].a = b;
            es[eee].b = a;
            es[eee++].cost = c;
        }
        for(int i = 0; i < w; i++){
            scanf("%d %d %d", &a, &b, &c);
            es[eee].a = a;
            es[eee].b = b;
            es[eee++].cost = -c;
        }
        if(bell()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}