【BZOJ2330】【SCOI2011】糖果

在cf上转悠的时候莫名突然想到了差分约束。。【不要问我为什么

然后去问r_64神犇

然后就学了一下差分约束系统

然后就刷了一道板子题

差分约束系统大概就是把约束条件变成边然后跑最短/长路。。。

也还挺简单的【也真是太神了

有的时候要判断能否成立就判断一下有没有正/负权环即可。

// <2330.cpp> - 02/21/16 15:07:12
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=100002;
int n;
vector <pair<int,int> > b[MAXN];
void ins(int x,int y,int k){b[x].push_back(make_pair(y,k));}
queue <int> q;
bool inq[MAXN];
int dis[MAXN],times[MAXN];
bool SPFA(){
	for(int i=1;i<=n;i++){dis[i]=1;q.push(i);inq[i]=1;}
	while(!q.empty()){
		int now=q.front();q.pop();inq[now]=0;
		for(int i=0;i<b[now].size();i++){
			int next=b[now][i].first;
			if(dis[now]+b[now][i].second>dis[next]){
				if(++times[next]==n)return 0;
				dis[next]=dis[now]+b[now][i].second;
				if(!inq[next]){q.push(next);inq[next]=1;}
			}
		}
	}
	return 1;
}
int main(){
	n=getint();
	int k=getint();
	for(int i=0;i<k;i++){
		int c=getint(),x=getint(),y=getint();
		if(c==1){ins(x,y,0);ins(y,x,0);}
		else if(c==2)ins(x,y,1);
		else if(c==3)ins(y,x,0);
		else if(c==4)ins(y,x,1);
		else if(c==5)ins(x,y,0);
	}
	if(!SPFA()){printf("-1");return 0;}
	lol ans=0;
	for(int i=1;i<=n;i++)ans+=dis[i];
	cout<<ans;
	return 0;
}

// <2330.cpp> - 02/21/16 15:07:12

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100002;

int n;

vector <pair<int,int> > b[MAXN];

void ins(int x,int y,int k){b[x].push_back(make_pair(y,k));}

queue <int> q;

bool inq[MAXN];

int dis[MAXN],times[MAXN];

bool SPFA(){

for(int i=1;i<=n;i++){dis[i]=1;q.push(i);inq[i]=1;}

while(!q.empty()){

int now=q.front();q.pop();inq[now]=0;

for(int i=0;i<b[now].size();i++){

int next=b[now][i].first;

if(dis[now]+b[now][i].second>dis[next]){

if(++times[next]==n)return 0;

dis[next]=dis[now]+b[now][i].second;

if(!inq[next]){q.push(next);inq[next]=1;}

}

return 1;

}

int main(){

n=getint();

int k=getint();

for(int i=0;i<k;i++){

int c=getint(),x=getint(),y=getint();

if(c==1){ins(x,y,0);ins(y,x,0);}

else if(c==2)ins(x,y,1);

else if(c==3)ins(y,x,0);

else if(c==4)ins(y,x,1);

else if(c==5)ins(x,y,0);

}

if(!SPFA()){printf("-1");return 0;}

lol ans=0;

for(int i=1;i<=n;i++)ans+=dis[i];

cout<<ans;

return 0;

}