题面

点击此处前往原题。

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。

John 的每个农场有 $m$ 条小路(无向边)连接着 $n$ 块地(从 $1 \sim n$ 标号),并有 $w$ 个虫洞。

现在 John 想借助这些虫洞来回到过去(出发时刻之前),请你告诉他能办到吗。

题解

SPFA判断负环板子。

代码

#include <bits/stdc++.h>
#define MANX 505
using namespace std;
struct node {
    int dis, nex;
} f;
vector< node > mp[MANX];
int sum[MANX], fl[MANX] = { 0 }, flag;
void spfa( int k ) {
    if ( fl[k] == 1 ) {
        fl[k] = 0;
        flag = 1;
        return;
    }
    fl[k] = 1;
    if ( !mp[k].empty() )
        for ( int i = 0; i < mp[k].size(); i++ ) {
            if ( sum[mp[k][i].nex] > mp[k][i].dis + sum[k] ) {
                sum[mp[k][i].nex] = mp[k][i].dis + sum[k];
                spfa( mp[k][i].nex );
                if ( flag == 1 ) {
                    fl[k] = 0;
                    return;
                }
            }
        }
    fl[k] = 0;
}
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    int test, m, n = 0, w, x, y, z, k;
    cin >> test;
    while ( test-- ) {
        for(unsigned int i=1;i<=n;i++){
            mp[i].clear();
        } 
        cin >> n >> m >> k;
        for ( int i = 1; i <= m; i++ ) {  
            cin >> x >> y >> z;
            f.dis = z;
            f.nex = y;
            mp[x].push_back( f );
            f.nex = x;
            mp[y].push_back( f );
        }
        for ( int i = 1; i <= k; i++ ) {
            cin >> x >> y >> z;
            f.dis = -z;
            f.nex = y;
            mp[x].push_back( f );
        }
        memset( sum, 0, sizeof( sum ) );
        flag = 0;
        for ( int i = 1; i <= n; i++ ) {
            spfa( i );
            if ( flag ) {
                break;
            }
        }
        if ( flag == 1 ) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}
Last modification:October 23, 2020
如果您觉得我的文章有用,给颗糖糖吧~