《真的有人会做差分约束吗》
by rangertank @ 2024-04-22 21:58:24
啊对，你没用链式前向星 @[ybc2026_sutongyan](/user/948757)
by rangertank @ 2024-04-22 22:08:37
我把你这个代码拿过去测试不会被棕吧
by rangertank @ 2024-04-22 22:09:16
@[ybc2026_sutongyan](/user/948757)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e6+10;
ll h[N],e[N],ne[N],w[N],idx,n,m,dist[N],q[N],cnt[N];
bool st[N];
void add(ll a,ll b,ll c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
bool spfa(){
memset(dist,-0x3f,sizeof dist);
int hh=0,tt=1;
dist[0]=0;
q[0]=0;
st[0]=true;
while(hh<=tt){
auto t=q[--tt];
st[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]=cnt[t]+1;
if(cnt[j]>=n+1) return false;
if(!st[j]){
q[tt++]=j;
st[j]=true;
}
}
}
}
return true;
}
int main(){
memset(h,-1,sizeof h);
memset(st,0,sizeof st);
cin>>n>>m;
while(m--){
ll x,a,b;
cin>>x>>a>>b;
if(x==1) add(b,a,0),add(a,b,0);
else if(x==2) add(a,b,1);
else if(x==3) add(b,a,0);
else if(x==4) add(b,a,1);
else add(a,b,0);
}
for(ll i=1;i<=n;i++) add(0,i,1);
bool t=spfa();
if(!t){
cout<<"-1";
return 0;
}
ll res=0;
for(ll i=1;i<=n;i++){
res+=dist[i];
}
cout<<res;
return 0;
}
by rangertank @ 2024-04-22 22:42:42
链式前向星可以100pts，但是subtask还要优化
by rangertank @ 2024-04-22 22:43:13