进阶指南_图论_lduoj_做题记录（下）-阿里云开发者社区

D. Sorting It All Out

Description

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A,B,C,D implies that A<B, B<C and C<D. in this problem, we will give you a set of relations of the form A<Band ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n

and m. the first value indicated the number of objects to sort, where 2≤n≤26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A<B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n=m=0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after xxx relations: yyy…y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

Samples

Input 复制

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

Output

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

考虑拓扑排序，有非常明显的从局部的特征到整体的特征之间的特点，拓扑排序可以跳转博客

因为数据范围足够小，并且题目要求输出循环次数，说明跑拓扑排序是完全没问题的

当入度为0的点有多个的情况下，可以得到答案不唯一的结果，当vector中的点的数量小于n的情况下，说明此时有1环，即有冲突，当以上两种情况均在循环中没有发生，即得不到答案

const int maxn = 1e6+7;
int n,m;
vector<int> vet;
int a[30][30];
int deg[30];
int teg[30];
string s[30000];
int topSort(){
    queue<int> que;
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(deg[i] == 0) que.push(i);
        teg[i] = deg[i];
    }
    vet.clear();
    int flag = 0;
    while(que.size()){
        if(que.size() > 1) flag = 1;
        int top = que.front();
        que.pop();
        int tot = 0;
        vet.push_back(top);
        for(int i=1;i<=n;i++){
            if(a[top][i]){
                teg[i] --;
                if(teg[i] == 0){
                    que.push(i);
                }
            }
        }
    }
    if(vet.size() < n) return 0;///huan
    if(flag == 1) return 1;///
    return 2;
}
int main()
{
    ///freopen("1.in","r",stdin);
    while(cin >> n >> m){
        if(n == 0 && m == 0) break;
        for(int i=1;i<=m;i++) cin >> s[i];
        int flag = 0;
        int siz;
        memset(a,0,sizeof a);
        memset(deg,0,sizeof deg);
        for(int i=1;i<=m;i++){
            int u = s[i][0];
            int v = s[i][2];
            u -= 'A'; u ++;
            v -= 'A'; v ++;
            deg[v] ++;
            a[u][v] = 1;
            siz = topSort();
            if(siz == 2){
                printf("Sorted sequence determined after %d relations: ",i);
                for(int i=0;i<n;i++) printf("%c",vet[i] + 'A' - 1);
                puts(".");
                flag = 1;
                break;
            }
            else if(siz == 0){
                printf("Inconsistency found after %d relations.\n",i);
                flag = 1;
                break;
            }
        }
        if(flag == 0) puts("Sorted sequence cannot be determined.");
    }
    return 0;
}

F. 走廊泼水节

Description

给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。我们一共有N个OIER打算参加这个泼水节，同时很凑巧的是正好有N个水龙头(至于为什么，我不解释)。N个水龙头之间正好有N−1条小道，并且每个水龙头都可以经过小道到达其他水龙头(这是一棵树，你应该懂的…)。但是OIER门为了迎接中中的挑战，决定修建一些个道路(至于怎么修，秘密～),使得每个水龙头到每个水龙头之间都有一条直接的道路连接(也就是构成一个完全图呗～)。但是OIER门很懒得，并且记性也不好，他们只会去走那N-1条小道，并且希望所有水龙头之间修建的道路，都要大于两个水龙头之前连接的所有小道(小道当然要是最短的了)。所以神COW们，帮那些OIER们计算一下吧，修建的那些道路总长度最短是多少，毕竟修建道路是要破费的～

Input

多组数据，第一行t，表示有t组测试数据，对于每组数据：第一行N，表示水龙头的个数（当然也是OIER的个数）；

2到N行，每行三个整数X,Y,Z；表示水龙头X和水龙头Y有一条长度为Z的小道

Output

对于每组数据，输出一个整数，表示修建的所有道路总长度的最短值。

Samples

Input

Output

4
17

Hint

第一组数据，在2和3之间修建一条长度为4的道路，是这棵树变成一个完全图，且原来的树依然是这个图的唯一最小生成树.

每个测试点最多10组测试数据

50%: n≤1500;

100%: n≤6000

100%: z≤100

克鲁斯卡尔思想，分享一片比较好的博文

要用到并查集维护联通块，如果说再给两个本来不连通的连通块连上一条边之后，增加的边的数量是siz_a * siz_b - 1;

因为还不能破坏之前存在的最小生成树（假设边权为w）,那么来说新增加的边权至少是w + 1;

const int maxn = 5e5 + 7;
const double eps = 1e-6;
int n, m;
int T;
struct node
{
    int u, v, w;
} e[maxn];
bool cmp(node a, node b)
{
    return a.w < b.w;
}
int fa[maxn];
int find(int x)
{
    if(x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}
int siz[maxn];
void init()
{
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
        siz[i] = 1;
    }
}
int main()
{
    cin >> T;
    while(T --)
    {
        n = read;
        init();
        for(int i = 1; i < n; i++)
        {
            e[i].u = read, e[i].v = read, e[i].w = read;
        }
        ll ans = 0;
        sort(e + 1, e + n, cmp);
        for(int i = 1; i < n; i++)
        {
            int fau = find(e[i].u);
            int fav = find(e[i].v);
            if(fau == fav) continue;
            else
            {
                fa[fau] = fav;
                ans += (e[i].w + 1) * (siz[fau] * siz[fav] - 1);
                siz[fav] += siz[fau];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

G. 黑暗城堡

Description

在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。现在lqr已经搞清楚黑暗城堡有N

个房间 (1≤N≤1000)，M条可以制造的双向通道，以及每条通道的长度。

lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的；但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：设 D[i] 为如果所有的通道都被修建，第 i 号房间与第1号房间的最短路径长度；而 S[i] 为实际修建的树形城堡中第 i 号房间与第1号房间的路径长度；要求对于所有整数 i(1≤i≤N)，有 S[i]=D[i] 成立。

为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。于是lqr向applepi提出了这个问题。因为applepi还要忙着出模拟赛，所以这个任务就交给你了。当然，你只需要输出答案对 231–1取模之后的结果就行了。

Input

第一行有两个整数N和M。

之后M 行，每行三个整数X,Y 和L，表示可以修建X 和Y之间的一条长度为L 的通道。

Output

一个整数，表示答案对 231–1

取模之后的结果。

Samples

Input 复制

Output

Hint

对于30% 的数据，2≤N≤5，M≤10。

对于50% 的数据，满足条件的方案数不超过10000。

对于100% 的数据，2≤N≤1000，N–1≤M≤N(N–1)/2，1≤L≤100

n的数据范围比较小，n 2 也是可以的，dijstra(),求出来最短路之后，可以直接使用乘法原理加取膜进行操作就好

const int maxn = 1e6+7;
struct node{
    int v;
    int w;
    int nex;
}e[maxn];
bool vis[maxn];
ll dis[maxn];
int head[maxn];
int cnt = 0;
int n,m;
typedef pair<int,int> PII;
void init(){
    for(int i=1;i<=n;i++){
        dis[i] = 0x3f3f3f3f;
        head[i] = -1;
        vis[i] = 0;
    }
}
void add(int u,int v,int w){
    e[cnt].v = v;
    e[cnt].nex = head[u];
    e[cnt].w = w;
    head[u] = cnt++;
}
void Dijkstra(int x){
    dis[x] = 0;
    priority_queue<PII,vector<PII>,greater<PII> > que;
    que.push({dis[x],x});
    while(que.size()){
        PII cur = que.top();
        que.pop();
        int u = cur.second;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i=head[u];~i;i = e[i].nex){
            int v = e[i].v;
            int w = e[i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                que.push({dis[v],v});
            }
        }
    }
}
ll ans = 1;
const ll mod = (1L << 31) - 1L;
int main()
{
    cin >>n >> m;
    init();
    for(int i = 1;i<=m;i++){
        int u,v,w; cin >> u >> v >> w;
        add(u,v,w);
        add(v,u,w);
    }
    Dijkstra(1);
    for(int i=2;i<=n;i++){
        int cnt = 0;
        for(int j = head[i];~j;j = e[j].nex){
            int v = e[j].v;
            int w = e[j].w;
            if(dis[i] == dis[v] + w){
                cnt ++;
            }
        }
        ans = (ans * cnt) % mod;
        ans %= mod;
    }
    cout<<ans<<'\n';
    return 0;
}

进阶指南_图论_lduoj_做题记录（下）

D. Sorting It All Out

Description

Input

Output

Samples

F. 走廊泼水节

Description

Input

Output

Samples

Hint

G. 黑暗城堡

Description

Input

Output

Samples

Hint

热门文章

最新文章

相关课程

相关电子书