UOJ #282 糖果

【题目描述】:

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

PS:出题人/搬题人太毒,建图顺序不对会导致#5会TLE/WA。。。
【输入描述】:

输人的第一行是两个整数N,K。

接下来K行,表示这些点需要满足的关系,每行3个数字,X,A,B。

如X=1,表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多。

如X=2,表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果。

如X=3,表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果。

如X=4,表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果。

如X=5,表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果。
【输出描述】:

输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。
【样例输入】:

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

【样例输出】:

11

【时间限制、数据范围及描述】:

时间:1s 空间:128M

对于30%的数据,保证N<=100。

对于100%的数据,保证N<=100,000。

对于所有的数据,保证K<=100,000;1<=X<=5;1<=A,B<=N。

本题可以将所有不等号改为大于等于号(a>b改为a-b>=1),然后跑最长路求最小糖果数即可。 Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<queue>
using namespace std;
const int N=2000005,INF=1000000005;
int n,k,opt,Cnt,dis[N],vis[N],head[N],use[N];
long long ans;
struct Edge{
    int u,v,w,Next;
}Edge[N];
void Push(int u,int v,int w){
    Edge[++Cnt].Next=head[u];
    Edge[Cnt].v=v;
    Edge[Cnt].w=w;
    head[u]=Cnt;
}
int SPFA(int s){
    queue<int> q;
    for(int i=1;i<=n;i++){
        dis[i]=-1;
        vis[i]=0;
    }
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        use[u]++;
        if(use[u]>n){
            return 0;
        }
        vis[u]=0;
        for(int i=head[u];i;i=Edge[i].Next){
            int v=Edge[i].v; 
            if(dis[v]<dis[u]+Edge[i].w){
                dis[v]=dis[u]+Edge[i].w;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[n]==-1){
        return 0;
    }
    return 1;
}
int main(){
    int opt,u,v;
    scanf("%d %d",&n,&k);
    int s=0;
    for(int i=n;i>=1;i--){
        Push(s,i,1);
    }
    for(int i=1;i<=k;i++){
        scanf("%d %d %d",&opt,&u,&v);
        if(opt==1){
            Push(u,v,0);
            Push(v,u,0);
        }
        else if(opt==2){
            Push(u,v,1);
        }
        else if(opt==3){
            Push(v,u,0);
        }
        else if(opt==4){
            Push(v,u,1);
        }
        else if(opt==5){
            Push(u,v,0);
        }
        else if(opt%2==0&&u==v){
            printf("-1\n");
            return 0;
        }
    }
    if(!SPFA(s)){
        printf("-1\n");
        return 0;
    }
    for(int i=1;i<=n;i++){
        ans+=dis[i];
    }
    printf("%lld\n",ans);
    return 0;
}
上一篇:vue3常用 Composition API


下一篇:Python连接DB2数据库基本