70pts
查看原帖
70pts
728090
RaynorLzj楼主2024/7/26 20:02

各位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;
}

2024/7/26 20:02
加载中...