[BZOJ2330][SCOI2011]糖果差分约束系统+最短路

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2330

类似于题目中这种含有不等式关系，我们可以建立差分约束系统来跑最长路或最短路。

对于一个不等式$X_1-X_2>=a$我们可以看成是$X_1>=X_2+a$，把$X_1$和$X_2$看成两个点，我们可以发现这个关系跟最长路中的$dis[v]>=dis[u]+w[i]$很像，就是最长路中的点一定满足这样的关系。

所以我们就按着这个思路，先把关于点$X_1$，$X_2$和边$a$的图建好，再来跑一遍最长路，如果有解，就一定满足题目中的不等式关系。

具体连边方式就是若有$a>=b+c$，则连$b$到$a$，边权为$c$。最短路同理。

最长路无解的情况就是存在正权环，最短路存在负权环。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int INF=<<;

 int inline readint(){

     int Num;char ch;

     while((ch=getchar())<''||ch>'');Num=ch-'';

     while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';

     return Num;

 }

 int N,K;

 int to[],ne[],w[],fir[],cnt=;

 void Add(int a,int b,int c){

     to[++cnt]=b;

     w[cnt]=c;

     ne[cnt]=fir[a];

     fir[a]=cnt;

 }

 int vis[],dis[];

 bool in[];

 queue <int> q;

 ll spfa(){

     for(int i=;i<=N;i++) dis[i]=-INF;

     in[N+]=true;

     q.push(N+);

     dis[N+]=;

     vis[N+]=;

     int u;

     while(!q.empty()){

         u=q.front();

         q.pop();

         in[u]=false;

         for(int i=fir[u];i!=-;i=ne[i]){

             int v=to[i];

             if(dis[v]<dis[u]+w[i]){

                 dis[v]=dis[u]+w[i];

                 if(!in[v]){

                     q.push(v);

                     in[v]=true;

                     vis[v]++;

                     if(vis[v]>N) return -;

                 }

             }

         }

     }

     ll ans=;

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

     return ans;

 }

 int main(){

     memset(fir,-,sizeof(fir));

     N=readint();

     K=readint();

     for(int i=;i<=K;i++){

         int X=readint(),

             A=readint(),

             B=readint();

         switch(X){

             case :

                 Add(B,A,);

                 Add(A,B,);

                 break;

             case :

                 if(A==B){

                     puts("-1");

                     return ;

                 }

                 Add(A,B,);

                 break;

             case :

                 Add(B,A,);

                 break;

             case :

                 if(A==B){

                     puts("-1");

                     return ;

                 }

                 Add(B,A,);

                 break;

             case :

                 Add(A,B,);

                 break;

         }

     }

     for(int i=N;i>=;i--) Add(N+,i,);

     printf("%lld\n",spfa());

     return ;

 }

巴特西

[BZOJ2330][SCOI2011]糖果差分约束系统+最短路

最新文章

热门文章

巴特西

[BZOJ2330][SCOI2011]糖果 差分约束系统+最短路

最新文章

热门文章

[BZOJ2330][SCOI2011]糖果差分约束系统+最短路