拓扑排序


Problem
Description 
自从Lele开荒了Rating系统,他的Tetris工作越来越如虎傅翼,不久她遍把这一个娱乐推向了稠人广众。 

title: Fruit

为了越来越好的符合那个爱好者的喜好,Lele又想了1个新点子:他将营造2在那之中外Tetris高手排名榜,按期更新,名堂要比Forbes富豪榜还响。关于什么排行,那一个毫无说都晓得是基于Rating从高到低来排,假设两个人有所一样的Rating,那就按这几人的RP从高到低来排。 

tags: [acm,杭电,母函数]

难点链接

Problem Description

一转眼到了获得的季节,由于有TT的正规化指点,Lele得到了大丰收。尤其是鲜果,Lele1共种了N种水果,有苹果,梨子,大蕉,西瓜……不但味道鲜美,样子更是美观。
于是乎,繁多芸芸众生向往而来,找Lele买水果。
乃至连资深的HDU ACM总御史 lcy
也来了。lcy抛出一打百元大钞,”作者要买由M个水果组成的果品拼盘,但是小编有个非常的小意求,对于种种水果,个数上本身有限定,既无法简单有个别特定值,也不可能越过有个别特定值。而且自个儿决不两份同样的小吃。你轻便搭配,你能组出多少种不相同的方案,小编就买多少份!”
今日就请您帮帮Lele,帮他算壹算到底能够卖出多少份水果拼盘给lcy了。
注意,水果是以个为着力单位,不可见再分。对于两种方案,即使各个水果的数量都1律,则感到那两种方案是平等的。
提起底Lele拿了这笔钱,又有啥不可继续她的学业了~

 

Input

本标题包蕴多组测试,请处理到文件结束(EOF)。
每组测试第三行李包裹含八个正整数N和M(含义见标题叙述,0<N,M<=100)
接下去有N行水果的新闻,每行多少个整数A,B(0<=A<=B<=拾0),表示至少要买该水果A个,至多只好买该水果B个。

 

Output

对此每组测试,在一行里输出总共能够卖的方案数。
标题数据保险那些答案小于十^九

 

Sample Input

2 3
1 2
1 2
3 5
0 3
0 3
0 3

 

Sample Output

2
12

好不轻松,Lele要伊始行动了,对N个人开始展览排名。为了便利起见,每种人都已经被编号,分别从0到N-壹,并且编号越大,RP就越高。 
并且Lele从狗仔队里赚取部分(M个)关于Rating的音讯。那些音信大概有三种情况,分别是”A
> B”,”A = B”,”A < B”,分别代表A的Rating高于B,等于B,小于B。 

分析

要么母函数难题,只是多了一些范围,稍微处理局地就行了。

今昔Lele并不是让您来帮他创制那几个高手榜,他只是想掌握,依据那一个音信是或不是能够鲜明出这几个高手榜,是的话就输出”OK”。不然就请你认清失误的来头,到底是因为音讯不完全(输出”UNCERTAIN”),依旧因为那几个信息中带有争持(输出”CONFLICT”)。 
专注,假如音讯中并且含有冲突且音讯不完全,就输出”CONFLICT”。 

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        vector<int>sum, value, a, b;
        for (int i = 0; i < n; i++)
        {
            int a1, b1;
            scanf("%d%d", &a1, &b1);
            a.push_back(a1);//最低限制
            b.push_back(b1);//最高限制
        }
        int c1[10050] = {0}, c2[10050] = {0};
        for (int i = a[0]; i <= b[0]; i++)//不再是从零开始了
            c1[i] = 1;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= m; j++)
                for (int k = a[i]; k + j <= m && k <= b[i]; k++)
                    c2[k + j] += c1[j];
            for (int i = 0; i <= m; i++)
            {
                c1[i] = c2[i];
                c2[i] = 0;
            }

        }
        printf("%d\n", c1[m]);
    }
    return 0;
}
/*
2 3
1 2
1 2
3 5
0 3
0 3
0 3
*/

Input 
本题目包涵多组测试,请管理到文件截至。 
每组测试第二行李包裹括多少个整数N,M(0<=N<=一千0,0<=M<=30000),分别代表要排行的总人口以及获得的关全面。 
接下去有M行,分别表示这么些关乎 

Output 
对于每组测试,在壹行里按标题要求输出 

Sample Input 
3 3 
0 > 1 
1 < 2 
0 > 2 
4 4 
1 = 2 
1 > 3 
2 > 0 
0 > 1 
3 3 
1 > 0 
1 > 2 
2 < 1 

Sample Output 
OK 
CONFLICT 
UNCERTAIN 

思路:把=号用并查集管理未来(全体同壹聚积的数字用根数字来代表,以集结根节点为单位充实边)正是显著的拓扑排序了 
所用知识: 
*如若叁回入队入度为零的点超越壹则表达拓扑排序连串不唯一,用分叉树去精通的话,就是同样层有多少个节点 
*纵然急需排序的总个数小于给定的个数,则阐明存在回路

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;

int pre[10005], L[20005], R[20005], ind[10005], n;    //L:左值,R:右值
char ch[20005];    //ch: 中值,ind: 入度

struct node{
    int son;    //儿子的编号
    node *next;    //指向下一个儿子,即为son的兄弟
}*N[10005];

int find (int a)        //并查集:寻找终极父节点,即a所属的集合的根节点
{
    while (a != pre[a])
        a = pre[a];
    return a;
}

void insert (int a, int b)    //b插入作为a的儿子,a这个链表表示a的所有儿子,不包括孙子
{
    node *p = new node;
    p->son = b;
    p->next = N[a];
    N[a] = p;
}

void init ()    //初始化
{
    int i;
    for (i = 0; i < n; i++)
    {
        pre[i] = i;
        ind[i] = 0;
        N[i] = NULL;
    }
}

int main()
{
    int i, A, B, m, num;
    while (~scanf ("%d%d", &n, &m))
    {
        init ();
        num = n;    //num是需要排序的点的个数
        for (i = 0; i < m; i++)
        {
            scanf ("%d %c %d", L+i, ch+i, R+i);
            if (ch[i] == '=')    //=则合并为同一集合
            {
                A = find (L[i]);
                B = find (R[i]);
                if (A != B)    //需要排序的个数-1,既然相等就不需要进行拓扑了,顺序已定
                    pre[B] = A, num--;
            }
        }
        bool flag = false;
        for (i = 0; i < m; i++)    //合并完之后才可以进行以下操作
        {
            if (ch[i] == '=')    //=的情况刚刚已经处理完
                continue;
            A = find (L[i]);
            B = find (R[i]);
            if (A == B)
            {//两个值属于同一集合,也就是刚刚上面相等合并为同一集合,现在却不等了,矛盾!
                flag = true;
                break;    //矛盾就可以直接退出循环了
            }
            if (ch[i] == '>')
            {
                insert (A, B);    //注意,必须用A,B(即集合的根节点)进行入边操作
                ind[B]++;   //入度+1
            }
            else
            {
                insert (B, A);    //同理
                ind[A]++;
            }
        }
        if (flag)
        {
            puts ("CONFLICT");    //矛盾
            continue;
        }
        queue<int> q;
        for (i = 0; i < n; i++)
            if (ind[i] == 0 && i == find(i))
                q.push (i);    //找到拓扑排序的终极父亲,入度为0,且为集合根节点
        while (!q.empty())
        {
            if (q.size() > 1)//(类似于分叉的树)同一层有多个点,则必有多个拓扑排序序列
                flag = true;
            num--;   //排好一个点了
            int t = q.front();
            q.pop();
            for (node *i = N[t]; i; i = i->next)
                if (--ind[i->son] == 0)//入度为1才可入队列,为了防止重复入队列,自减
                    q.push (i->son);
        }
        if (num > 0)    //根据题意,优先判断是否矛盾
            puts ("CONFLICT");
        else if (flag)    //有多个拓扑排序序列,所以不确定
            puts ("UNCERTAIN");
        else puts ("OK");
    }
    return 0;
}

 

相关文章