首页 > 代码库 > bzoj 2330 糖果

bzoj 2330 糖果

2024-08-16 19:14:00   212人阅读

差分约束系统：

　　给出有n个变量和m个约束条件（形如ai-aj<=k的不等式）的系统，求出满足这些约束条件的一组变量

　　那么……思路是把数的模型转换成图的模型，求解一个单源最短路径问题：

　　当有ai-aj<=k这个条件时，即在图中创建一条从aj指向ai的有向边，设置边权为k

　　然而还要创建一个起点，可以把它理解为一个基点，它连向每一个点，边权均为0

　　最后执行Bellman-ford或者SPFA等算法，求得{di}为答案

奉上裸题一道：

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

题解：

　　取等时创建边权为0的边，不取等时创建边权为1的边

注意：据hzw大神题解，有一个数据是十万个点形成长链，给基点加边的时候需做从n到1的循环，否则会炸

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define MAXN 100010 6 int heads[MAXN],cnt,q[MAXN*5],d[MAXN],t[MAXN],n,k;//t记录结点进队次数 7 long long ans=0; 8 bool vis[MAXN]; 9 struct node10 {11     int v,val,next;12 }edge[3*MAXN];13 void add(int x,int y,int z)14 {15     edge[++cnt].v=y;16     edge[cnt].next=heads[x];17     heads[x]=cnt;18     edge[cnt].val=z;19 }20 bool SPFA()21 {22     int head=1,tail=2;23     vis[0]=true;24     q[head]=0;25     t[0]=1;26     while(head<tail)27     {28         for(int i=heads[q[head]];i!=0;i=edge[i].next)29         {30             if(d[edge[i].v]<d[q[head]]+edge[i].val)31             {32                 d[edge[i].v]=d[q[head]]+edge[i].val;33                 if(!vis[edge[i].v])34                 {35                     if(++t[edge[i].v]>=n)return false;//结点进队次数过n，判定有环36                     q[tail++]=edge[i].v;37                     vis[edge[i].v]=true;38                 }39             }40         }41         vis[q[head]]=false;42         head++;43     }44     return true;45 }46 int main()47 {48     int x,y,z;49     scanf("%d%d",&n,&k);50     for(int i=1;i<=k;i++)51     {52         scanf("%d%d%d",&z,&x,&y);53         if(z==1)54         {55             add(x,y,0);56             add(y,x,0);57         }58         else if(z==2)59         {60             if(x==y)61             {62                 printf("-1\n");//不存在自己给自己建边且边权为163                 return 0;64             }65             else add(x,y,1);66         }67         else if(z==3)add(y,x,0);68         else if(z==4)69         {70             if(x==y)71             {72                 printf("-1\n");73                 return 0;74             }75             else add(y,x,1);76         }77         else if(z==5)add(x,y,0);78     }79     for(int i=n;i>=1;i--)add(0,i,1);80     if(!SPFA())81     {82         printf("-1\n");83         return 0;84     }85     for(int i=1;i<=n;i++)ans+=d[i];86     printf("%lld\n",ans);87     return 0;88 }

*参考：http://baike.baidu.com/link?url=RAR0bFN3lF9u12-B-4qTiTOO7u6YuGQ_qXXNgEmosvKKH06ouY5ZbPsKwoT6o5ho5lPf7tgBA2kYWJjhge_k3q

bzoj 2330 糖果


联系
我们