学步园

题意： 有N种 货币，M个交易所，每个交易所互换两种货币，问给你第s种货币，你能否让它越换越多

其实就是找一条能够让他增值的正权回路，这个 用bellman-Ford，spfa 几乎都能做，不过我没试过

说一下思路：

用bellman-Ford，在dis[S]没有增值的情况下进行反向松弛（就是放大）；如果不能松弛了就退出来看一下有没有放大就可以了；（这样可以不用判断负环）

用spfa，思路同上......

习惯了用 链式前向小星星+spfa来写了

code

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 101;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
using namespace std;

int N, M, S, e_cnt, adj[maxn], cnt[maxn]; // cnt 用来判断是否存在付权回路
double V, dis[maxn];
bool vis[maxn];
struct Edge{
    int end, next;
    double  r, c; //r is rate ,c is commission
}Graph[maxn<<1];

void add_E(int start, int end, double r1, double c1, double r2, double c2){
    Graph[e_cnt].end=end;
    Graph[e_cnt].r=r1;
    Graph[e_cnt].c=c1;
    Graph[e_cnt].next=adj[start];
    adj[start]=e_cnt++;

    Graph[e_cnt].end=start;
    Graph[e_cnt].r=r2;
    Graph[e_cnt].c=c2;
    Graph[e_cnt].next=adj[end];
    adj[end]=e_cnt++;
}

bool spfa(){
    queue<int> q;
    vis[S]=true;
    q.push(S);
    cnt[S]=1;
    dis[S]=V;

    while(!q.empty()){
        int tmp=q.front();
        q.pop();

        vis[tmp]=false;

        for(int i=adj[tmp];i;i=Graph[i].next){
            double r=Graph[i].r;
            double c=Graph[i].c;
            int end=Graph[i].end;
            if(dis[end] < (dis[tmp]-c)*r){
                dis[end]=(dis[tmp]-c)*r;
                if(!vis[end]){
                    vis[end]=true;
                    if(++cnt[end]>N)
                        return true;
                    q.push(end);
                }
            }
        }

    }
    //printf("%lf  %lf \n",dis[S],V);
    return dis[S]>V;
}

int main(){
    e_cnt=1;
    scanf("%d%d%d%lf",&N,&M,&S,&V);
    FF(i,M){
       int A,B;
       double r1,c1,r2,c2;
       scanf("%d%d%lf%lf%lf%lf",&A,&B,&r1,&c1,&r2,&c2);
       add_E(A,B,r1,c1,r2,c2);
    }
    if(spfa()) puts("YES");
    else puts("NO");
	return 0;
}

下面是用bellman-ford写的

code：

/*
ID: yueqiq
PROG: numtri
LANG: C++
*/
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 101;
const int INF = 1111;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
int N,M,S,e_cnt;
double V,dis[maxn];
struct Edge{
    int s,e;
    double r,c;
}Graph[maxn<<1];
void add_E(int a,int b,double rab,double cab,double rba,double cba){
    Graph[e_cnt].s=a;
    Graph[e_cnt].c=cab;
    Graph[e_cnt].r=rab;
    Graph[e_cnt].e=b;
    e_cnt++;

    Graph[e_cnt].e=a;
    Graph[e_cnt].c=cba;
    Graph[e_cnt].r=rba;
    Graph[e_cnt].s=b;
    e_cnt++;
}
void readGraph(){
    e_cnt=1;
    scanf("%d%d%d%lf",&N,&M,&S,&V);
    int a,b;
    double rab,cab,rba,cba;
    FOR(i,1,M){
        scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
        add_E(a,b,rab,cab,rba,cba);
    }
}
bool bellman_ford(){
    SET(dis,0);
    dis[S]=V;
    bool flag;
    while(dis[S]<=V){
        flag=false;
        FOR(i,1,e_cnt-1){
            if(dis[Graph[i].e]<(dis[Graph[i].s]-Graph[i].c)*Graph[i].r){
                flag=true;
                dis[Graph[i].e]=(dis[Graph[i].s]-Graph[i].c)*Graph[i].r;
            }
        }
        //printf("dis S:%.2lf\n",dis[S]);
        if(!flag){
            if(dis[S]>V) return true;
            else return false;
        }
    }
    return true;
}
int main()
{
    readGraph();
    if(bellman_ford()) puts("YES");
    else puts("NO");
    return 0;
}