各位dalao麻烦看下哪里错了,只有70分,谢谢!
// Problem: P3275 [SCOI2011] 糖果
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3275
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Leizijin
//
// Powered by CP Editor (https://cpeditor.org)
// 差分约束SPFA要超时
// 看用差分约束思路构造的这图的性质
// 边权仅为0,1
// 考虑通过强连通分量将0边的点缩一下(缩成的点内糖果数相同)
// 然后考虑1边,此时是DAG,答案合法
// 否则不合法(有自环也不合法)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<ll,ll>
#define il inline
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int N = 2e5+5; // 对于x=1的情况会出现双向连边,所以数组开大一点
const int inf = 0x3f;
ll n,K,cnt;
struct Edge{
ll u, v;
ll type;
} M[N];
vector<pii> G[N], E[N];
ll dfn[N], low[N], SCC[N], TOP, sta[N], din[N], siz[N];
ll dist[N];
bool in_stack[N];
ll SCC_CNT, DFN_CNT;
il void Tarjan(int u){
dfn[u] = low[u] = ++DFN_CNT;
in_stack[u] = 1;
sta[++TOP] = u;
for(pii &edge : G[u]){
ll v = edge.first, w = edge.second;
if(w) continue;
if(!dfn[v]){
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(in_stack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
SCC[u] = ++SCC_CNT;
siz[SCC_CNT]++;
in_stack[u] = 0;
while(sta[TOP] != u){
SCC[sta[TOP]] = SCC_CNT;
siz[SCC_CNT]++;
in_stack[sta[TOP]] = 0;
TOP--;
}
TOP--;
}
}
bool TopoOrder(){ // 拓扑排序DP出最长路,(>=的不等条件)
memset(dist, inf, sizeof(dist));
queue<int> Q;
dist[SCC[n+1]] = 0;
Q.push(SCC[n+1]);
while(!Q.empty()){
int u = Q.front(); Q.pop();
// printf("%d\n", u);
for(pii &ed : E[u]){
int v = ed.first, w = ed.second;
din[v]--;
if(dist[u] + w < dist[v]){
dist[v] = dist[u] + w;
}
if(!din[v]) Q.push(v);
}
}
for(int i=1; i<=SCC_CNT; i++) if(din[i]) return false;
return true;
}
signed main(){
fastio;
cin >> n >> K;
for(int i=1,x,a,b; i<=K; i++){
cin >> x >> a >> b;
if(x == 1){ // 所有目标式:a + b >= c
// a=b ->
M[++cnt] = {a, b, 0};
M[++cnt] = {b, a, 0};
}
else if(x == 2){
// a < b -> a+1<=b -> b-1>=a
M[++cnt] = {b, a, -1};
}
else if(x == 3){
// a>=b -> a+0>=b
M[++cnt] = {a, b, 0};
}
else if(x == 4){
// a>b -> a>=b+1 -> a-1>=b
M[++cnt] = {a, b, -1};
}
else if(x == 5){
// a<=b -> a+0<=b -> b-0>=a
M[++cnt] = {b, a, 0};
}
else printf("zuosi!");
}
for(int i=1; i<=cnt; i++){
G[M[i].u].pb({M[i].v, M[i].type});
}
int S = n+1;
for(int i=1; i<=n; i++) G[S].pb({i, 0});
Tarjan(S);
// Rebuild Graph
for(int i=0,u,v,w; i<=S; i++){
u = SCC[i];
for(pii &ed : G[i]){
v = SCC[ed.first];
w = ed.second;
if(u==v && !w) continue;
E[u].pb({v, w});
din[v]++;
}
}
bool delta = TopoOrder();
if(delta){
ll mmin = 1e18;
for(int i=1; i<=SCC_CNT; i++){
mmin = min(mmin, dist[i]);
}
// printf("min: %lld\n", mmin);
ll ans = 0;
for(int i=1; i<=SCC_CNT; i++){
if(i == SCC[S]) continue; // 不需要处理
ans += 1ll * siz[i] * (1ll * dist[i] - mmin + 1);
// printf("%lld\n", 1ll * siz[i] * (1ll * dist[i] - mmin + 1));
}
printf("%lld\n", ans);
}
else{
printf("-1\n");
}
return 0;
}