zoj 2770 Burn the Linked Camp (差分约束系统)

// 差分约束系统
// 火烧连营 
// n个点 m条边 每天边约束i到j这些军营的人数  n个兵营都有容量
// Si表示前i个军营的总数 那么   1.Si-S(i-1)<=C[i]     这里 建边(i-1,i) 权值为 C[i]
//                          2.S(i-1)-Si<=0        这里 建边(i,i-1) 权值为 0
//                          3.S(j)-S(i-1)>=k  => S(i-1)-Sj<=-k 这里建边 (j,i-1) 权值为 -k
//  题目求的事 Sn-S0的最小值  Sn-S0>=m 中符合条件的m最大值就是答案
// 等价 S0-Sn<=-m  求点 Sn 到 S0的最小值  就是求最短路径  (这里可能不好理解，需要慢慢体会)
//   

#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MOD 1000000007
#define maxn 20010 // 开始我天真了 maxn=10010 和 m 差不错大 WA的好难过 图中边数应该为 m+2n   
#define MAX 100000000
struct node{
  int to;
  int next;
  int val;
}E[maxn];
int num;
int V[1010];
int C[1010];
int d[1010],cnt[1010];
bool f[1010];
bool sfpa(int s,int t){// s既表示起点 又表示节点个数
   queue <int> Q;
   int u,v;
   int e;
   Q.push(s);
   d[s]=0;
   f[s]=true;
   while(!Q.empty()){
    u=Q.front(); Q.pop();
    cnt[u]++;
    if(cnt[u]>s) return false;
    f[u]=false;
    for(e=V[u];e!=-1;e=E[e].next){
        v=E[e].to;
        if(d[u]+E[e].val<d[v]){
            d[v]=d[u]+E[e].val;
            if(!f[v])
            {
                f[v]=true;
                Q.push(v);
            }
        }
    }
   }
   return true;
}
int main(){
    int i,j,k;
    int n,m;
   while(scanf("%d %d",&n,&m)!=EOF){
     for(i=1;i<=n;i++)
        {
            scanf("%d",&C[i]);
            V[i]=-1;
            d[i]=MAX;
            cnt[i]=0;
            f[i]=false;
        }
        num=0;
        i=0;
        V[i]=-1;
        d[i]=MAX;
        cnt[i]=0;
        f[i]=false;
     while(m--){
        scanf("%d %d %d",&i,&j,&k);
        E[num].to=i-1;
        E[num].val=-k;
        E[num].next=V[j];
        V[j]=num++;
     }
     for(i=n;i>=1;i--){
        E[num].to=i;
        E[num].val=C[i];
        E[num].next=V[i-1];
        V[i-1]=num++;
        E[num].to=i-1;
        E[num].val=0;
        E[num].next=V[i];
        V[i]=num++;
     }
     if(sfpa(n,0))
         printf("%d
",-d[0]);
     else
        printf("Bad Estimations
");

   }

}
zoj 2770 Burn the Linked Camp (差分约束系统)

相关推荐
