[FOJ1898 Cows Arrangement]超Orz的差分约束系统~

【题目大意】
有一个数组d[1..n]
d[1]=0，d[i]然后给出一些限制，
第一种：x,y,w，d[y]-d[x]<=w（数据保证x第二种：x,y,w，d[y]-d[x]>=w（数据保证x一个d[i]=k满足条件当且仅当存在一组d[1..n]满足限制，而且d[i]=k。
【算法分析】
完全没想到。。。一开始写了个二分+差分判可行了。。。完全超时到天荒地老。。。
后来看正解。
非常Orz。就是按题目的这些不等式建图。
第一次，按最短路来建图，d[1]设为0，然后其他全设为无穷大。跑一遍最短路的spfa。
第二次，按最长路来建图，d[1]设为0，然后其他也全设为0。跑一遍最长路的spfa。

然后、然后、很Orz地他就解决了。。。

最短路跑出的是最大值。
最长路跑出的是最小值。

为什么呢？
因为他都是按照那个不等式最贴边的方式解得。
所以最短路就是刚好<=那个上界。
而最长路则是刚好>=那个下界。

So，Orz。。。。
【CODE】
#include #include #include #include #include using namespace std;
const int N=5005;
const int INF=100000000;
int n;
int L[N],R[N],d[N],Q[N],v[N],Inn[N];
bool flag;
struct edge{int x,y,w;edge *next;};
struct Link_t{
edge sp[N],*ls[N];
int e;
void init(){
e=0;
for (int i=1;i<=n;i++) ls[i]=NULL;
}

void addedge(int x,int y,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].w=w;
sp[e].next=ls[x]; ls[x]=&sp[e];
}
}Hate,Love,G;

void input(){
int ml,mh,i,x,y,w;
scanf("%d%d%d",&n,&ml,&mh);
Hate.init();
Love.init();
for (i=1;i<=ml;i++){
scanf("%d%d%d",&x,&y,&w);
Love.addedge(x,y,w);
}
for (i=1;i<=mh;i++){
scanf("%d%d%d",&x,&y,&w);
Hate.addedge(x,y,w);
}
}

void build1(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i G.addedge(i+1,i,-1);
G.addedge(1,n,INF);
}

void spfa1(){
for (int i=1;i<=n;i++){
Inn[i]=0;
v[i]=0;
d[i]=INF+22;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w d[t->y]=d[t->x]+t->w;
if (d[t->y]<0){
flag=false;
return;
}
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
Inn[t->y]++;
if (Inn[t->y]>n){
flag=false;
return;
}
}
}
v[Q[head]]=0;
}
}

void build2(){
G.init();
int i;
for (i=1;i<=Love.e;i++){
edge *t=&Love.sp[i];
G.addedge(t->y,t->x,-t->w);
}
for (i=1;i<=Hate.e;i++){
edge *t=&Hate.sp[i];
G.addedge(t->x,t->y,t->w);
}
for (i=1;i G.addedge(i,i+1,1);
G.addedge(n,1,-INF);
}

void spfa2(){
for (int i=1;i<=n;i++){
v[i]=0;
d[i]=0;
}
int head=0,tail=1;
d[1]=0; Q[1]=1; v[1]=1;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=G.ls[Q[head]];t;t=t->next)
if (d[t->x]+t->w>d[t->y]){
d[t->y]=d[t->x]+t->w;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
Q[tail]=t->y;
}
}
v[Q[head]]=0;
}
}

void output(){
puts("Exist!");
for (int i=1;i<=n;i++)
printf("%d %dn",L[i],R[i]);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
input();
flag=true;
build1();
spfa1();
if (!flag){
puts("Not Exist!");
continue;
}
for (int j=1;j<=n;j++) R[j]=d[j];
build2();
spfa2();
for (int j=1;j<=n;j++) L[j]=d[j];
output();
}
}