CQUPT 拓扑排序

题解

hdu2647 reward
题意：
有一个老板，他有n个员工，在发工资的时候，他的有些员工有要求，比如说a要求自己的工资要比b高。现在有m个要求，老板想用最少的钱去付工资。如果都能满足这些要求的话，输出最少的钱，否则输出-1.
思路：
拓扑排序，反向建图，（正向建图无法做）。最先我是用的双层循环，wa几发，时间复杂度是n^2，应该是t了，hdu好奇怪（可能是我本来就错了呢？
后来用队列来做，一次就过，以后都用队列了，实现起来也简单。
代码：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
int indr[10005];
int fee[10005];
vector<int> v[10005];
queue<int> qq;
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        while (!qq.empty()) qq.pop();
        memset(indr,0,sizeof(indr));
        memset(fee,0,sizeof(fee));
        memset(v,0,sizeof(v));
        for (int i = 1;i <= m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            indr[x]++;
            v[y].push_back(x);
        }
        int flag = 0;
        for (int i = 1;i <= n;i++)
            if (indr[i] == 0)
            {
                qq.push(i);
            }
        while (!qq.empty())
        {
            int mark = qq.front();
            qq.pop();
            for (int i = 0;i < v[mark].size();i++)
            {
                indr[v[mark][i]]--;
                fee[v[mark][i]] = fee[mark] + 1;
                if (indr[v[mark][i]] == 0) qq.push(v[mark][i]);
            }
        }
        for (int i = 1;i <= n;i++)
            if (indr[i] != 0) flag = 1;
        if (flag) printf("-1\n");
        else
        {
            long long sum = 0;
            for (int i = 1;i <= n;i++)
                sum += (fee[i]+888);
            printf("%lld\n",sum);
        }
    }
    return 0;
}

poj1386 play on words
题意：
输入是n行字符串，用相当于词语接龙的方法，上一个字符串的最后一个字符与后一个字符串的第一个字符相同，用完所有的字符，问是否可能。
思路：
如果把字母当成节点，单词当成边的话，那么我们的任务就是找到一条欧拉路或者欧拉回路。（如何想到的？。。。）
用并查集判断图的联通很方便。
算法：
存在欧拉（回）路的条件：
1底图联通
2欧拉路：只存在两个节点的度为奇数，其余为偶数，且度数为奇数的节点中，一个入度比出度大1，一个出度比入度大1.
3欧拉回路：所有的点的度均为偶数。
代码：

#include <stdio.h>
#include <string.h>
int vis[26];
int g[26][26];
int iv[26];
int ov[26];
int res = 0;
void dfs(int v)
{
    vis[v] = 1;
    res++;
    for (int i = 0;i < 26;i++)
    {
        if (g[v][i] && !vis[i])
            dfs(i);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n;
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        memset(g,0,sizeof(g));
        memset(iv,0,sizeof(iv));
        memset(ov,0,sizeof(ov));
        char s[1005];
        for (int i = 0;i < n;i++)
        {
            res = 0;
            scanf("%s",s);
            int len = strlen(s) - 1;
            int in = s[len] - 'a';
            int out = s[0] - 'a';
            g[in][out] = g[out][in] = 1;
            iv[in]++;
            ov[out]++;
        }
        int num = 0,st = 0,en = 0,word = 0,mark;
        for (int i = 0;i < 26;i++)
        {
            if (iv[i] || ov[i])
            {
                word++;
                mark = i;
            }
            if (iv[i] && ov[i] && iv[i] == ov[i]) num++;
            if (iv[i] - ov[i] == 1) en++;
            if (ov[i] - iv[i] == 1) st++;
        }
        bool flag = 0;
        if (num == word) flag = 1;
        else if (num == word-2 && en == 1 && st == 1) flag = 1;
        dfs(mark);
        if (res != word) flag = 0; 
        if (flag) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
    return 0;
}

hdu1811:rank of tetris
题意：中文，略
思路：
一开始，就想到用拓扑排序，但是对于冲突并没有完全理解，以为只要按照关系可以写出拓扑序就不是矛盾，但是是错误的。
比如第二个样例
1 = 2
1 > 3
2 > 0
0 > 1
2 > 0 与 0 > 1 推出的是2 > 1 与第一个条件矛盾了，这样也称为矛盾。
后来看了题解才知道，可以用并查集来表示相等的关系。为什么可以这样做呢？当我们用根来进行了正确的拓扑排序之后，一个集合中的元素因为有rp的高低，所以也能进行正确的排序，这样就证明了用并查集表示的合理性。
其次，我以前用拓扑排序判断环，是进行了排序之后检查所有的点的入度是否都为0，有不为0的就判断有环，其实这样做是有漏洞的（虽然不知道是什么）。有一种更好的判断环的方法，就是确定进行拓扑排序的点的总数是否与点的总数相等，这样非常的方便，因为我在进行拓扑排序的时候就可以记录点数。第二点呢，就是判断是否有多个拓扑序存在，即当队列中超过一个点时，就说明入度为0的点有多个，就证明了有多个拓扑序。
还有就是每次写并查集一定要写init函数啊，不要忘记了。
代码：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[10005];
queue<int> mmp;
int in[10005];
int par[10005];
struct node
{
    int p,q;
    char op;
};
typedef struct node node;
node rate[10005];
int fin(int x)
{
    if (par[x] == x)
        return x;
    else
        return par[x] = fin(par[x]);
}
bool unit(int x,int y)
{
    x = fin(x);
    y = fin(y);
    if (x != y)
    {
        par[x] = y;
        return 1;
    }
    return 0;
}
void init(void)
{
    for (int i = 0;i < 10005;i++)
        par[i] = i;
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        int sum = n;
        bool con = 0,unc = 0;
        memset(rate,0,sizeof(rate));
        memset(v,0,sizeof(v));
        memset(in,0,sizeof(in));
        memset(par,0,sizeof(par));
        while (!mmp.empty()) mmp.pop();
        init();
        for (int i = 1;i <= m;i++)
        {
            scanf("%d %c %d",&rate[i].p,&rate[i].op,&rate[i].q);
            if (rate[i].op == '=')
            {
                if (unit(rate[i].p,rate[i].q))
                    --sum;
            }
        }
        for (int i = 1;i <= m;i++)
        {
            int tx =  rate[i].p,ty = rate[i].q;
            tx = fin(tx);
            ty = fin(ty);
            if (rate[i].op == '>')
            {
                in[tx]++;
                v[ty].push_back(tx);
            }
            else if (rate[i].op == '<')
            {
                in[ty]++;
                v[tx].push_back(ty);
            }
        }
        for (int i = 0;i < n;i++)
        {
            if (i == fin(i) && in[i] == 0)
                mmp.push(i);
        }
        while (!mmp.empty())
        {
            if (mmp.size() > 1) unc = 1;
            int tmp = mmp.front();
            mmp.pop();
            for (int j = 0;j < v[tmp].size();j++)
            {
                int tp = v[tmp][j];
                in[tp]--;
                if (!in[tp]) mmp.push(tp);
            }
            --sum;
        }
        if (sum > 0) con = 1;
        if (con)
        {
            printf("CONFLICT\n");
            continue;
        }
        if (unc)
        {
            printf("UNCERTAIN\n");
            continue;
        }
        printf("OK\n");
    }
    return 0;
}

HDU5883:The best path
题意：
有n个湖，m条河，每个湖有一个值，找一条一笔画可以经过每一条河一次，且找出这条路线的每个湖的值的异或值最大。
思路：
一笔画，欧拉路，然而这并不是重点。
坑：
这才是重点！！！！！！！！！！！！
首先，这是一个无向图，然而我把它当成了有向图去处理。
第二，这些湖可能有些湖是孤立的，因为河水并不一定要连到湖。。。想的吐血了。。。
第三，就是孤立的湖，我们不能计算它的贡献。。。。
新姿势：
如果一个数异或偶数次，那么结果是0
0异或任何数都是这个数本身。
如果一个数列是确定的，那么异或的顺序不影响结果。
难点：
对于欧拉通路，起点和终点的贡献加一次，所以判断每个点是否有贡献，我们可以用(d[i]+1)/2%2是否为1进行判断，举个例子，假如起点的度是7次，那么就是经过3次，还有1次（孤立的），所以一共4次，实际没有贡献，用上述的公式算出来的就是8/2%2就是0；再如一个终点的度数为5，那么就是经过了完整的两次加上1次，共3次，所以有贡献，上述算出来也是3.对于偶数度的点，不会有丝毫的影响，1在/的时候就已经gg了。
新得：
不知道女装做题是否可以减少bug啊。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int du[100005];
int va[100005];
int par[100005];
void init(int n)
{
    for (int i = 0;i <= n;i++)
        par[i] = i;
}
int fin(int x)
{
    if (x == par[x])
        return x;
    else
        return par[x] = fin(par[x]);
}
void unit(int x,int y)
{
    x = fin(x);
    y = fin(y);
    if (x != y)
        par[x] = y;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(du,0,sizeof(du));
        memset(va,0,sizeof(va));
        memset(par,0,sizeof(par));
        init(n);
        for (int i = 1;i <= n;i++)
        {
            scanf("%d",&va[i]);
        }
        for (int i = 1;i <= m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            unit(x,y);
            du[x]++;
            du[y]++;
        }
        int fa;
        for (int i = 1;i <= n;i++)
        {
            if (du[i]) fa = i;
        }
        fa = fin(fa);
        int flag = 1;
        for (int i = 1;i <= n;i++)
        {
            if (du[i] && fa != fin(i)) flag = 0;
        }
        if (!flag)
        {
            //printf("@\n");
            printf("Impossible\n");
            continue;
        }
        int odd = 0;
        for (int i = 1;i <= n;i++)
        {
            if (du[i] % 2) odd++;
        }
        bool tl = 0,hl = 0;
        if (odd == 0) hl = 1;
        else if (odd == 2) tl = 1;
        else flag = 0;
        if (!flag)
        {
            printf("Impossible\n");
            continue;
        }
        int ans = 0;
        for (int i = 1;i <= n;i++)
        {
            if ((du[i]+1) / 2 % 2) ans ^= va[i];
        }
        int tmp = ans;
        if (hl)
        {
            for (int i = 1;i <= n;i++)
                if (du[i])
                    ans = max(ans,tmp^va[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}