首页 > 代码库 > CDOJ 435 (SCOI 2011) 糖果 Label:差分约束系统

CDOJ 435 (SCOI 2011) 糖果 Label:差分约束系统

2024-08-15 15:26:26   219人阅读

糖果

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 131072/131072KB (Java/Others)

Submit Status

幼儿园里有NN个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数N(1≤N≤1000001≤N≤100000)，K(1≤K≤1000001≤K≤100000)。

接下来KK行，表示这些点需要满足的关系，每行33个数字，X，A，B(1≤X≤51≤X≤5, 1≤A,B≤N1≤A,B≤N)。

  • 如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；
  • 如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；
  • 如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；
  • 如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；
  • 如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；

Output

输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出−1。

Sample input and output

Sample Input

Sample Output

5 7

1 1 2

2 3 2

4 4 1

3 4 5

5 4 5

2 3 5

4 5 1

11

 

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #define ll long long 8 #define INF 0x3f3f3f3f 9 #define MAXN 20000510 using namespace std;11 12 int N,M,tot;13 int inq[MAXN],dis[MAXN],cur[MAXN];14 vector<int> G[MAXN],c[MAXN];15 queue<int> q;16 17 void add(int u,int v,int w){18     G[u].push_back(v);19     c[u].push_back(w);20 }21 22 ll sum(){23     ll tmp=0;24     for(int i=1;i<=N;i++)25         tmp+=dis[i];26     return tmp;27 } 28 29 int spfa(){30     q.push(0);inq[0]=1;31     while(!q.empty()){32         int x=q.front();q.pop();33         for(int i=0;i<G[x].size();i++){34             int to=G[x][i];35             if(dis[to]<dis[x]+c[x][i]){//最长路 36                 dis[to]=dis[x]+c[x][i];37                 if(++cur[to]>=N) return 0;38                 if(!inq[to]){39                     q.push(to);40                     inq[to]=1;41                 }42             }43         }44         inq[x]=0;45     }46     return 1;47 }48 49 int main(){50 //    freopen("01.in","r",stdin);51     scanf("%d%d",&N,&M);52     for(int i=1;i<=M;i++){53         int op,x,y;54         scanf("%d%d%d",&op,&x,&y);55         switch(op){56             case 1:{57                 add(x,y,0);58                 add(y,x,0);//Orz59                 break;60             }61             case 2:{62                 if(x==y){puts("-1");return 0;}//Orz63                 add(x,y,1);64                 break;65             }66             case 3:{67                 add(y,x,0);68                 break;69             }70             case 4:{71                 if(x==y){puts("-1");return 0;}//Orz72                 add(y,x,1);73                 break;74             }75             case 5:{76                 add(x,y,0);77                 break;78             }79         }80     }81     for(int i=1;i<=N;i++) add(0,i,1);//每个小朋友都要分到 82     83     if(!spfa()) puts("-1");84     else printf("%lld\n",sum());//long long85     86     return 0;87 }

 

CDOJ 435 (SCOI 2011) 糖果 Label:差分约束系统


联系
我们