P4042 [AHOI2014/JSOI2014]骑士游戏

一开始就想到全部扔进队列之后SPFA玄学松弛，觉得会T想了半天别的做法，一看题解竟然就是SPFA，觉得可以练手结果写了写发现暴力又好写，如果不开O²甚至需要加register才能过

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x)
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
LL read(){LL x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double PI = acos(-1.0);
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
vector<int>P[maxn],Q[maxn];
LL a[maxn],b[maxn];
LL dp[maxn];
bool vis[maxn];
inline void SPFA(){
    queue<int>Qu;
    for(int i = 1; i <= N ; i ++){
        vis[i] = 1;
        Qu.push(i);
    }
    while(!Qu.empty()){
        int u = Qu.front(); Qu.pop();
        vis[u] = 0;
        LL sum = a[u];
        for(register int i = 0; i < P[u].size(); i ++){
            int v = P[u][i];
            sum += dp[v];
        }
        if(sum >= dp[u]) continue;
        dp[u] = sum;
        for(register int i = 0 ; i < Q[u].size(); i ++){
            int v = Q[u][i];
            if(!vis[v]){
                Qu.push(v);
                vis[v] = 1;
            }
        }
    }
}
int main(){
    Sca(N);
    for(int i = 1; i <= N ; i ++){
        a[i] = read(); dp[i] = read();
        int K = read();
        while(K--){
            int x = read();
            P[i].pb(x); Q[x].pb(i);
        }
    }
    SPFA();
    Prl(dp[1]);
    return 0;
}

View Code

P2189 小Z的传感器

初看以为是一道很有操作的题，仔细一看q的范围只有5

那么每次询问先将所有没有传感器的房间用并查集连起来，然后依次每个点询问能否有一条边和初始点的并查集相连即可。

P2416 泡芙

没有口胡出来看了题解

将整个图用tarjan边双缩点然后求树链和是否 >= 1即可

口胡

赛前口胡题合集

P4042 [AHOI2014/JSOI2014]骑士游戏

P2189 小Z的传感器

P2416 泡芙