topsort    发布于 2020-03-08   963人围观   0条评论

题目大意

有s种动物排成一个长度为n的队伍,有l种朋友关系a b,动物a和动物b为朋友可以互相交换位置,但是当且仅当这两种动物在相邻位置时。

问在所有的可能交换位置的方案后,序列最小的字典序排列是什么。

题解

挺难想的一个题,看题解只有一句话,看代码看了好久才想明白。

通过动物之间的朋友关系,我们可以确定可以互相交换的有哪些位置,也可以确定哪些动物的相对位置是不能发生改变的。

于是我们可以利用不是朋友的动物之间的相对位置不能发生改变这一点,来进行拓扑排序(当然是字典序更小的动物为更优先序的)

首先给所有物种的名字排序保证是字典序,然后用二维数组E:0 表示两个物种可以交换(是朋友),1表示不能交换(不是朋友)、二维数组Fij:0表示物种i的当前最前位置的一个在物种j当前最前位置的前面,1则相反。

然后枚举每个位置放哪个物种,如果当前物种i满足有一个j使得Eij & Fij = 1,那么就说明这个物种当前最前面的个体之前有不能与其交换的个体,就不能在当前这个位置放这个物种的这个个体,就需要放其它物种。如果满足没有这样的j,那么这个位置就放物种i了(这时字典序一定最小),然后更新一下Fij(因为是Fij表示的是两物种当前未被放入序列种的最靠前的个题之间的位置关系),继续枚举下一位置放什么就可以了。

E和F由于只需要&操作,所以可以用bitset来进行加速。

代码

#include <bits/stdc++.h>
using namespace std;
int s,l,n;
const int maxn = 205;
vector<int>pos[maxn];
string a,b;
vector<string>name;
int id(string str){
   return lower_bound(name.begin(),name.end(),str) - name.begin(); 
}
bitset<maxn>e[maxn],f[maxn];
vector<int>ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s >> l >> n;
    name.reserve(s);
    for(int i = 0;i < s;++i){
        cin >> a;
查看更多
bitset topsort    发布于 2019-10-12   168人围观   0条评论


题目大意

给定一个n个点的DAG(有向无环图),每个点一开始都是白色,每一次操作会改变一个指定的点的颜色,并询问当前有多少对白点对(u,v)互相可达(存在一条从u到v的有向路径使得路径上全部为白色的点)。

题解

可以认为黑色点与其他点都不连通。

所以我们每一次更改点的颜色实际都是再更改图的联通关系。

我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系(这时候就通过位运算或|来代替Floyd原先的+就好了,因为位运算或即为逻辑加操作)。

但是我们发现这样复杂度是不对的……

这三种最快的topsort复杂度也是O(qnm)的,明显不符合我们的复杂度要求。

这时候我们注意到对于联通关系,两点间的联通关系也即用0表示不连通,1表示联通。

我们对于更新也是这样的:

假设当前检索点为u,下一个点为v,则对于所有联通u的点k,假设mp[i][j]表示是否可从i联通到j,则有

mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];

可以看到这个更新过程实际上只有位运算的或操作,只有0和1的运算,所以可以用bitset进行加速。

当我们检索到当前的点u时,先预处理设定mp[u][u] = 1,表示当前点可以到达当前点。最终因为答案是算不相同的点u和v联通个数,所以最后进行统计的时候答案整体-n即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
    for(int i = 1;i <= n;++i)
        con[i].reset();
    for(int i = 1;i <= n;++i){
        if(!c[i])
            con[i][i] = 1;
        vis[i] = 0;
    }
    for(int i = 1;i <= n;++i){
        tmp[i] = d[i];
      
查看更多
topsort DP    发布于 2019-07-07   330人围观   0条评论

题解

别问我为什么写这么水的题解,问就是为了那门水的不行的专业选修课。

很简单,这个图肯定是个DAG(请不要问为什么,自己看一下题目描述。。。)

然后我们在这个DAG上按拓扑序来进行DP就可以了,因为入度为0的点一定最多游览一个,然后不断类似SPFA最长路一样的进行DP,就可以求出到某个城市最多可以游览的城市数目了。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n,m;
int x,y;
const int maxn = 1e5+5;
vector<int>g[maxn];
int f[maxn],d[maxn];
int inq[maxn];
int main(){
    memset(d,0,sizeof(d));
    n = get_num();
    m = get_num();
    for(int i = 1;i <= m;++i){
        x = get_num();
        y = get_num();
        g[x].push_back(y);
        d[y]++;
    }
    queue<int>q;
    for(int i = 1;i <= n;++i){
        if(!d[i])
            q.push(i),inq[i] = 1;
        f[i] = 1;
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
查看更多
topsort    发布于 2019-02-26   177人围观   0条评论

Description

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

Output

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

Sampl

查看更多
2-SAT tarjan topsort    发布于 2019-02-07   444人围观   0条评论

Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

查看更多