我最喜欢的题目就是简单题了。（没办法我是蒟蒻）
差分约束现学现卖
这题搞个差分约束，注意数据有个超长的链，倒着加边就行。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
//不要问为什么每个数组都是1000005……因为方便~
int n,k,en,h[1000005],cir[1000005],d[1000005],flg[1000005];
long long ans=0;
struct Edge{
int b,v,next;
}e[1000005];
void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
int spfa(){
//memset(d,0x3f,sizeof(d));
queue<int> Q;
Q.push(0);
d[0]=0;
flg[0]=1;
cir[0]=1;
int u,v;
while(!Q.empty()){
u=Q.front();
Q.pop();
flg[u]=0;
for(int i=h[u];i;i=e[i].next){
v=e[i].b;
if(d[u]+e[i].v>d[v]){
d[v]=d[u]+e[i].v;
if(++cir[v]>=n)return 1;
if(!flg[v]){
Q.push(v);
flg[v]=1;
}
}
}
}
return 0;
}
int main(){
freopen("2330.in","r",stdin);
freopen("2330.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++){
int x,a,b;
scanf("%d %d %d",&x,&a,&b);
if(x==1){add(a,b,0);add(b,a,0);continue;}
if(x==2){if(a==b){printf("-1\n");return 0;}add(a,b,1);continue;}
if(x==3){add(b,a,0);continue;}
if(x==4){if(a==b){printf("-1\n");return 0;}add(b,a,1);continue;}
if(x==5){add(a,b,0);continue;}
}
for(int i=n;i>0;i--)add(0,i,1);
if(spfa()){printf("-1\n");return 0;}
//for(int i=1;i<=n;i++)printf("%d\n",d[i]);
for(int i=1;i<=n;i++)ans+=d[i];
printf("%lld\n",ans);
return 0;
}
评论 (0)
