最关键的就是找好所有的要满足的不等式条件，注意隐含的条件还有一点就是注意没有源点 建立源点
#2436. 「SCOI2011」糖果
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define int long long
const int N = 5e5+10,M = 2e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
int dist[N];
bool vis[N];
int cnt[N];
int e[M],ne[M],w[M],h[N],idx;
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
void spfa()
{
stack<int>q;
memset(dist,-0x3f,sizeof dist);
dist[0] = 0;
vis[0] = true;
q.push(0);
//int count = 0;
while(q.size()){
auto t = q.top();
q.pop();
vis[t] = false;
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(dist[j]<dist[t]+w[i]){
dist[j] = dist[t]+w[i];
cnt[j]++;
if(cnt[j]>=n){cout<<-1;return;}
//if(++count>100000){cout<<-1;return;}
if(!vis[j]){
vis[j] = true;
q.push(j);
}
}
}
}
int res = 0;
for(int i=1;i<=n;i++)res+=dist[i];
cout<<res;
}
void solve()
{
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
int a,b,c;cin>>c>>a>>b;
if(c==1){add(a,b,0),add(b,a,0);}
else if(c==2){add(a,b,1);}
else if(c==3){add(b,a,0);}
else if(c==4){add(b,a,1);}
else add(a,b,0);
}
for(int i=1;i<=n;i++)add(0,i,1);
spfa();
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}
#10087. 「一本通 3.4 例 1」Intervals
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define int long long
const int N = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
int e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
int dist[N];
bool vis[N];
int mx;
void spfa()
{
memset(dist,-0x3f,sizeof dist);
queue<int>q;
q.push(0);
dist[0] = 0;
vis[0] = true;
while(q.size()){
auto t = q.front();
q.pop();
vis[t] = false;
//cout<<t<<"\n";
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(dist[j]<dist[t]+w[i]){
dist[j] = dist[t]+w[i];
if(!vis[j]){
vis[j] = true;
q.push(j);
}
}
}
}
cout<<dist[50001];
}
void solve()
{
memset(h,-1,sizeof h);
cin>>m;
for(int i=1;i<=50001;++i){
add(i-1,i,0),add(i,i-1,-1);
}
while(m--){
int a,b,c;cin>>a>>b>>c;
a++,b++;
add(a-1,b,c);
}
spfa();
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}
#10090. 「一本通 3.4 练习 2」布局 Layout
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define int long long
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m1,m2;
int dist[N],cnt[N];
bool vis[N];
int e[N],ne[N],w[N],h[N],idx;
void add(int a,int b,int c){
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}
bool spfa(int sz)
{
memset(dist,0x3,sizeof dist);
memset(cnt,0,sizeof cnt);
memset(vis,0,sizeof vis);
queue<int>q;
for(int i=1;i<=sz;++i){
dist[i] = 0;
q.push(i);
vis[i] = true;
}
while(q.size()){
auto t = q.front();
q.pop();
vis[t] = false;
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(dist[j]>dist[t]+w[i]){
dist[j] = dist[t]+w[i];
cnt[j]++;
if(cnt[j]>=n)return true;
if(!vis[j]){
vis[j] = true;
q.push(j);
}
}
}
}
return false;
}
void solve()
{
cin>>n>>m1>>m2;
memset(h,-1,sizeof h);
for(int i=0;i<=n;++i)add(i+1,i,0);
while(m1--){
int a,b,c;cin>>a>>b>>c;if(a>b)swap(a,b);
add(a,b,c);
}
while(m2--){
int a,b,c;cin>>a>>b>>c;if(a>b)swap(a,b);
add(b,a,-c);
}
if(spfa(n))cout<<-1;
else{
spfa(1);
if(dist[n]>inf/2)cout<<-2;
else cout<<dist[n];
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}
