96-84: 模板练习

三分
libreoj #10013
二分
libreoj #10011 #10012 #10014
生成树
libreoj #10068 #10066
spfa+优化
libreoj #10081 #10085
差分约束
libreoj #10087
Tarjan相关
libreoj #10094 #10095 #10098
负环
luogu 3385

三分

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

#define D double

const D del = 1e-10;

int n;
D A[N], B[N], C[N];

D Calc(D x) {
    D Max = -1e18;
    Rep(i, 1, n) Max = max(Max, A[i] * x * x + B[i] * x + C[i]);
    return Max;
}

int main() {
    int T; cin >> T;
    Rep(tt, 1, T) {
        cin >> n;
        Rep(i, 1, n) scanf("%lf%lf%lf", &A[i], &B[i], &C[i]);
        D l = 0, r = 1000;
        while(l + del < r) {
            D lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
            if(Calc(lmid) < Calc(rmid)) r = rmid;
            else l = lmid;
        }
        printf("%.4lf
", Calc(r));
    }
    return 0;
}

负环

#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 100086
#define clear(a) memset(a,0,sizeof a)
#define rk for(RI i=1;i<=n;i++)
using namespace std;
IL void read(int &x) {
    int f=1;
    x=0;
    char s=getchar();
    while(s>'9'||s<'0') {
        if(s=='-')f=-1;
        s=getchar();
    }
    while(s<='9'&&s>='0') {
        x=x*10+s-'0';
        s=getchar();
    }
    x*=f;
}
int n,m,T;
struct code {
    int u,v,w;
} edge[N];
bool vis[N];
int head[N],tot,dis[N],cnt[N];
IL void add(int x,int y,int z) {
    edge[++tot].u=head[x];
    edge[tot].v=y;
    edge[tot].w=z;
    head[x]=tot;
}
IL bool spfa(int now) {
    rk vis[i]=false,dis[i]=(1 << 30),cnt[i]=false;
    queue<int>q;
    q.push(now);
    vis[now]=true;
    dis[now]=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(RI i=head[u]; i; i=edge[i].u) {
            if(dis[edge[i].v]>dis[u]+edge[i].w) {
                dis[edge[i].v]=dis[u]+edge[i].w;
                if(!vis[edge[i].v]) {
                    q.push(edge[i].v);
                    vis[edge[i].v]=true;
                    cnt[edge[i].v]++;
                    if(cnt[edge[i].v]>=n)return true;
                }
            }
        }
    }
    return false;
}
int main() {
    read(T);
    while(T--) {
        read(n),read(m);
        tot=0;
        clear(head);
        for(RI i=1,u,v,w; i<=m; i++) {
            read(u),read(v),read(w);
            if(w<0)add(u,v,w);
            else add(u,v,w),add(v,u,w);
        }
        puts(spfa(1)?"YE5":"N0");
    }
}