DQS DQS

HIT Summer Training Day7 tarjan|拓扑排序

in 算法,tarjan,图论,拓扑排序,模拟赛read (185) 文章转载请注明来源!

能复制板子真的太爽了!!

还是弱,推公式的题WA到死不会做……可能是因为智商低吧

A~F以及L是tarjan,G~K是拓扑排序。


A : poj - 2553

问缩点后入度为0的强连通分量中包含哪些点。

板子题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

stack<int> s;
int sccnum[SZ],scccnt = 0,sccsz[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void dfs(int u)
{
    dfn[u] = low[u]= ++ dfs_clock;
    s.push(u);
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!sccnum[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scccnt ++;
        while(233)
        {
            int x = s.top(); s.pop();
            sccnum[x] = scccnt;
            sccsz[scccnt] ++;
            if(x == u) break;
        }
    }
}

int ff[SZ],tt[SZ],cd[SZ];

int main()
{
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        memset(dfn,0,sizeof(dfn));
        memset(sccnum,0,sizeof(sccnum));
        memset(sccsz,0,sizeof(sccsz));
        memset(low,0,sizeof(low));
        memset(cd,0,sizeof(cd));
        memset(head,0,sizeof(head)); tot = 1;
        scccnt = 0,dfs_clock = 0;

        for(int i = 1;i <= m;i ++)
            scanf("%d%d",&ff[i],&tt[i]),build(ff[i],tt[i]);
        for(int i = 1;i <= n;i ++)
            if(!dfn[i])
                dfs(i);
        for(int i = 1;i <= m;i ++)
            if(sccnum[ff[i]] != sccnum[tt[i]])
                cd[sccnum[ff[i]]] ++;
        int t = 0,x,sz = 0;
        for(int i = 1;i <= scccnt;i ++)
            if(cd[i] == 0)
                t ++,x = i,sz = sccsz[i];
        //if(t == 1)
        //{
            for(int i = 1;i <= n;i ++)
                if(cd[sccnum[i]] == 0)
                    printf("%d ",i);
        //}
    //    else
            puts("");
    }
    return 0;
}


B : poj - 1523

问一个图中去掉某个割点剩下多少联通块。

求割点的时候记录一下:

如果是非根节点,答案是low[v]>=low[u]的个数+1(因为有父边)

如果是根节点,那么是儿子的个数。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 10010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t;
}l[SZ];

void build(int f,int t)
{
    l[++ tot].t = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int ans[SZ];
bool rt[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void tarjan(int u,int fa)
{
    dfn[u] = low[u]= ++ dfs_clock;
    int c = 0;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(fa == v) continue;
        if(!dfn[v])
        {
            c ++;
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(!rt[u] && low[v] >= dfn[u])
                ans[u] ++;
        }
        else if(dfn[v] < dfn[u])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(rt[u] && c > 1)
        ans[u] = c - 1;
}

int main()
{
    int cc = 0;
    while(233)
    {
        n = 0;
        dfs_clock = 0;
        memset(head,0,sizeof(head)); tot = 1;
        memset(ans,0,sizeof(ans));
        memset(rt,0,sizeof(rt));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        int u,v;
        scanf("%d",&u);
        if(u == 0) break;
        scanf("%d",&v);
        build(u,v); build(v,u);
        n = max(u,v);
        while(scanf("%d",&u) && u)
        {
            scanf("%d",&v);
            build(u,v); build(v,u);
            n = max(u,v);
        }
        for(int i = 1;i <= n;i ++)
            if(!dfn[i])
                rt[i] = 1,tarjan(i,0);
        bool flag = 0;
        for(int i = 1;i <= n;i ++)
            if(ans[i])
                flag = 1;
        printf("Network #%d\n",++ cc);
        if(!flag) puts("  No SPF nodes");
        else
        {
            for(int i = 1;i <= n;i ++)
                if(ans[i])
                    printf("  SPF node %d leaves %d subnets\n",i,ans[i] + 1);
        }
        puts("");
    }
    return 0;
}


C : poj - 1236

给一个有向图,问最少添加多少边能让整个图变为一个强连通分量。

缩点后,另入度为0的点为n,出度为0的点为m。

对于任意一对出入度为0的点,可以添加一个出度为0的点到入度为0的点的一条边。

两两消去后这样剩下了一些点,这些点是孤立的,每个点都要向一个根节点连边。

这样答案是$max{n,m}$。

还需要特判整张图只有个点的情况。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

stack<int> s;
int sccnum[SZ],scccnt = 0,sccsz[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void dfs(int u)
{
    dfn[u] = low[u]= ++ dfs_clock;
    s.push(u);
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
            dfs(v),low[u] = min(low[u],low[v]);
        else if(!sccnum[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        scccnt ++;
        while(233)
        {
            int x = s.top(); s.pop();
            sccnum[x] = scccnt;
            sccsz[scccnt] ++;
            if(x == u) break;
        }
    }
}

int ff[SZ],tt[SZ],cd[SZ],rd[SZ];

int fa[SZ];

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void Union(int a,int b)
{
    int x = find(a),y = find(b);
    if(x != y) fa[x] = y;
}

int rdcnt[SZ];

int main()
{
    scanf("%d",&n); m = 1;
    for(int i = 1;i <= n;i ++)
    {
        while(tt[m] = read())
            ff[m] = i,build(ff[m],tt[m]),m ++;
    }
    m --;
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            dfs(i);
    for(int i = 1;i <= scccnt;i ++) fa[i] = i;
    for(int i = 1;i <= m;i ++)
        if(sccnum[ff[i]] != sccnum[tt[i]])
            cd[sccnum[ff[i]]] ++,rd[sccnum[tt[i]]] ++,Union(sccnum[ff[i]],sccnum[tt[i]]);


    for(int i = 1;i <= scccnt;i ++)
        if(rd[i] == 0)
            rdcnt[find(i)] ++;

    int ans = 0,ltk = 0;
    for(int i = 1;i <= scccnt;i ++)
        if(find(i) == i)
            ans += rdcnt[i] - 1,ltk ++;

    int a0 = 0,b = 0,a = 0;
    for(int i = 1;i <= scccnt;i ++)
    {
    //    if(rd[i] == 0 && cd[i] == 0) { a0 ++; continue;}
        if(rd[i] == 0)  a ++;
        if(cd[i] == 0)  b ++;
    }
    printf("%d\n",a);
    if(scccnt == 1) puts("0");
    else printf("%d",max(a,b));
    /*if(a == 0 && b == 0)
    {
        if(a0 == 1) printf("0");
        else printf("%d",a0);
    }
    else
    {
        printf("%d",b + a0 + ans);
    }*/
    return 0;
}



D : codeforces - 427C

给一个有向图,一个点可以管辖他所在的scc中所有点。每个点设置管辖点有一个花费。

问最小花费管辖所有点,以及这个花费的方案数。

scc里对花费取min,然后乘法原理……

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 1000000007;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

stack<int> s;
int sccnum[SZ],scccnt = 0,sccsz[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;
vector<int> g[SZ];


void dfs(int u)
{
    dfn[u] = low[u]= ++ dfs_clock;
    s.push(u);
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!sccnum[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scccnt ++;
        while(233)
        {
            int x = s.top(); s.pop();
            sccnum[x] = scccnt;
            g[scccnt].push_back(x);
            sccsz[scccnt] ++;
            if(x == u) break;
        }
    }
}

int ff[SZ],tt[SZ],cd[SZ];
LL a[SZ];
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        a[i] = read();
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
        ff[i] = read(),tt[i] = read(),build(ff[i],tt[i]);
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            dfs(i);

    LL ans1 = 0,ans2 = 1;
    for(int i = 1;i <= scccnt;i ++)
    {
        LL minn = INF;
        for(int j = 0;j < g[i].size();j ++)
            minn = min(minn,a[g[i][j]]);
        ans1 += minn;
        LL t = 0;
        for(int j = 0;j < g[i].size();j ++)
            if(a[g[i][j]] == minn)
                t ++;
        ans2 = ans2 * t % mod;
    }
    printf("%I64d %I64d\n",ans1,ans2);
    return 0;
}


E : LYDSY - 1051

水题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

stack<int> s;
int sccnum[SZ],scccnt = 0,sccsz[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void dfs(int u)
{
    dfn[u] = low[u]= ++ dfs_clock;
    s.push(u);
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u],low[v]);
        }
        else if(!sccnum[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scccnt ++;
        while(233)
        {
            int x = s.top(); s.pop();
            sccnum[x] = scccnt;
            sccsz[scccnt] ++;
            if(x == u) break;
        }
    }
}

int ff[SZ],tt[SZ],cd[SZ];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++)
        ff[i] = read(),tt[i] = read(),build(ff[i],tt[i]);
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            dfs(i);
    for(int i = 1;i <= m;i ++)
        if(sccnum[ff[i]] != sccnum[tt[i]])
            cd[sccnum[ff[i]]] ++;
    int t = 0,ans = 0;
    for(int i = 1;i <= scccnt;i ++)
    {
        if(cd[i] == 0)
        {
            t ++;
            ans += sccsz[i];
        }
    }
    if(t == 1) printf("%d\n",ans);
    else puts("0");
    return 0;
}


F : poj - 3352

给一个无向图,问最少添加多少边使得整张图没有桥。

边双缩点后就是一棵树。树上每条树边都是一个桥。

贪心的想:每次选择叶子节点连边。这样答案是(叶子数+1)/2个。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,id;
}l[SZ];

void build(int f,int t,int id)
{
    l[++ tot] = (edge){t,id};
    nxt[tot] = head[f];
    head[f] = tot;
}

int bcnt = 0,bri[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void tarjan(int u,int fa)
{
    dfn[u] = low[u]= ++ dfs_clock;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(fa == v) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]) bcnt ++,bri[l[i].id] = 1;
        }
        else if(dfn[v] < dfn[u])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
}

int c[SZ];

void dfs(int u,int color)
{
    c[u] = color;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(!bri[l[i].id] && !c[v])
        {
            dfs(v,color);
        }
    }
}

int ff[SZ],tt[SZ],du[SZ];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++)
    {
        ff[i] = read(),tt[i] = read();
        build(ff[i],tt[i],i); build(tt[i],ff[i],i);
    }
    for(int i = 1;i <= n;i ++)
        if(!dfn[i])
            tarjan(i,0);
    int ccnt = 0;
    for(int i = 1;i <= n;i ++)
        if(!c[i])
            dfs(i,++ ccnt);

    for(int i = 1;i <= m;i ++)
        if(c[ff[i]] != c[tt[i]])
            du[c[ff[i]]] ++,du[c[tt[i]]] ++;
    int ans = 0;
    for(int i = 1;i <= ccnt;i ++)
        if(du[i] == 1)
            ans ++;
    printf("%d\n",ans + 1 >> 1);
    return 0;
}


G : poj - 2367

裸的拓扑排序…

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,id;
}l[SZ];

void build(int f,int t)
{
    l[++ tot] = (edge){t};
    nxt[tot] = head[f];
    head[f] = tot;
}



int rd[SZ];
queue<int> q;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        int x;
        while(x = read())
            build(i,x),rd[x] ++;
    }
    for(int i = 1;i <= n;i ++)
        if(!rd[i]) q.push(i);
    while(q.size())
    {
        int u = q.front(); q.pop();
        printf("%d ",u);
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(-- rd[v] == 0) { q.push(v); }
        }
    }
    return 0;
}


H : codeforces - 510C

给你n个字符串,问有没有一个字母表顺序似的它们按字典序递增排列。

相邻字符串进行比较,第一个不相同的字符之间存在大小关系。可以建边之后跑拓扑排序,排序不成功说明有环,是false。

还要特判后一个字符串是前一个字符串的前缀的情况,是false。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 100010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,id;
}l[SZ];

void build(int f,int t)
{
    l[++ tot] = (edge){t};
    nxt[tot] = head[f];
    head[f] = tot;
}



int rd[SZ];
queue<int> q;

string s[SZ];
char str[SZ];
string ans;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%s",str);
        s[i] = str;
    }
    for(int i = 1;i <= n - 1;i ++)
    {
        int len = min(s[i].length(),s[i + 1].length());
        bool flag = 0;
        for(int j = 0;j < len;j ++)
        {
            if(s[i][j] != s[i + 1][j])
            {
                flag = 1;
                build(s[i][j],s[i + 1][j]);
                rd[s[i + 1][j]] ++;
                break;
            }
        }
        if(!flag)
        {
            if(s[i].length() > s[i + 1].length())
                { puts("Impossible"); return 0;}
        }
    }
    for(int i = 'a';i <= 'z';i ++)
        if(!rd[i]) q.push(i);
    while(q.size())
    {
        int u = q.front(); q.pop();
        ans += (char)u;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(-- rd[v] == 0) { q.push(v); }
        }
    }
    if(ans.length() != 26) puts("Impossible");
    else cout << ans;
    return 0;
}


I : poj - 1094

给出一些字母的大小关系,问在哪一组矛盾或者前几组就能确定顺序或者输出不能排序。

边给关系边做拓扑排序……

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 1010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,id;
}l[SZ];

void build(int f,int t)
{
    l[++ tot] = (edge){t};
    nxt[tot] = head[f];
    head[f] = tot;
}



int rd[SZ];
queue<int> q;

string s[SZ];
string ans;

int tmp[SZ];

bool topsort()
{
    while(q.size()) q.pop();
    ans.clear();
    for(int i = 'A';i <= 'A' + n - 1;i ++)
        tmp[i] = rd[i];
    int t = 0;
    for(int i = 'A';i <= 'A' + n - 1;i ++)
        if(!tmp[i]) q.push(i),t ++;
    if(t != 1) return false;
    while(q.size())
    {
        int u = q.front(); q.pop();
        ans += (char)u;
        t = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(-- tmp[v] == 0) { q.push(v); t ++; }
        }
    //    cout << t << " " <<ans << endl;
        if(t != 1 && ans.length() != n) return false;
    }
    return true;
}

bool dfs(int u,int e)
{
    if(u == e) return true;
    for(int i = head[u];i;i = nxt[i])
    {
        if(dfs(l[i].t,e)) return true;
    }
    return false;
}

char str[SZ];

int main()
{
    while(~scanf("%d%d",&n,&m) && n)
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(rd,0,sizeof(rd));
        for(int i = 1;i <= m;i ++)
        {
            scanf("%s",str);
            s[i] = str;
        }
        bool flag = 0;
        for(int i = 1;i <= m;i ++)
        {
            int u = s[i][0],v = s[i][2];
            if(dfs(v,u))
            {
                flag = 1;
                printf("Inconsistency found after %d relations.\n",i);
                break;
            }
            build(u,v); rd[v] ++;
            if(topsort())
            {
                flag = 1;
                cout << "Sorted sequence determined after " << i << " relations: " << ans << ".\n";
                break;
            }
        }
        if(!flag)
            puts("Sorted sequence cannot be determined.");
    }
    return 0;
}
/*
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
*/


J : poj - 2585

有9个程序,每种程序的出现位置固定。由于出现次序不同会有不同的覆盖情况。给出最终的覆盖情况,问是否存在一种覆盖方案使得可以得到这个情况。

一开始读错题了,以为每种程序可以任意放……感觉很难写就弃题了……非常后悔……

对于一个程序本来在的地方,如果有其他程序,那么说明有一个程序覆盖关系。这样就有一个先后次序,可以建图跑拓扑排序。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 1010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int head[SZ],nxt[SZ],tot = 1,to[SZ];

void build(int f,int t)
{
//    cout << f << " " << t << endl;
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

struct haha
{
    int x,y;
};

vector<haha> g[SZ];

int rd[SZ];
queue<int> q;

bool toposort()
{
    while(q.size()) q.pop();
    for(int i = 1;i <= 9;i ++)
        if(!rd[i]) q.push(i);
    int ans = 0;
    while(q.size())
    {
        int u = q.front(); q.pop();
        ans ++;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i];
            if(-- rd[v] == 0) { q.push(v); }
        }
    }
    if(ans != 9) return false;
    return true;
}

int mp[SZ][SZ];
char str[SZ];

int main()
{
    for(int i = 1,t = 0;i <= 3;i ++)
        for(int j = 1;j <= 3;j ++)
            g[++ t].push_back((haha){i,j}),
            g[t].push_back((haha){i + 1,j}),
            g[t].push_back((haha){i,j + 1}),
            g[t].push_back((haha){i + 1,j + 1});
    while(~scanf("%s",str) && str[0] != 'E')
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(rd,0,sizeof(rd));
        for(int i = 1;i <= 4;i ++)
            for(int j = 1;j <= 4;j ++)
                scanf("%d",&mp[i][j]);
        for(int i = 1;i <= 9;i ++)
            for(int j = 0;j < 4;j ++)
                if(mp[g[i][j].x][g[i][j].y] != i)
                    build(i,mp[g[i][j].x][g[i][j].y]),rd[mp[g[i][j].x][g[i][j].y]] ++;
        if(toposort()) puts("THESE WINDOWS ARE CLEAN");
        else puts("THESE WINDOWS ARE BROKEN");
        scanf("%s",str);
    }
    return 0;
}
/*

*/


K : codeforces - 515D

给一个n*m的地图,图上每个点要么为空要么有障碍。问能不能用1*2的骨牌填满空白处并且方案唯一。

因为n,m<=2000所以不能跑网络流…………

对于一个点,其相邻的空白点记为这个点的度数。每次取出度数为1的点尝试去放。因为度数为1所以只有一个相邻点,于是就放置在这两个点上,并对周围的度数减1。这样做一个类似拓扑排序的东西,若成环说明有多解。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 2010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
const char ans1[] = {'<','^','>','v'};
const char ans2[] = {'>','v','<','^'};


LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int N,M;

char mp[SZ][SZ];
int du[SZ][SZ];

struct haha
{
    int x,y;
};

queue<haha> q;

void push(int sx,int sy)
{
    for(int k = 0;k < 4;k ++)
    {
        int x = sx + dx[k];
        int y = sy + dy[k];
        if(x >= 1 && x <= N && y >= 1 && y <= M && mp[x][y] == '.')
            if(-- du[x][y] == 1)
                q.push((haha){x,y});
    }
}

bool toposort()
{
    for(int i = 1;i <= N;i ++)
        for(int j = 1;j <= M;j ++)
            if(du[i][j] == 1)
                q.push((haha){i,j});
    while(q.size())
    {
        int sx = q.front().x,sy = q.front().y; q.pop();
        for(int k = 0;k < 4;k ++)
        {
            int x = sx + dx[k];
            int y = sy + dy[k];
            if(x >= 1 && x <= N && y >= 1 && y <= M && mp[x][y] == '.')
            {
                mp[sx][sy] = ans1[k],mp[x][y] = ans2[k];
                du[x][y] = du[sx][sy] = 0;
                push(x,y);
            }
        }
    }
    for(int i = 1;i <= N;i ++)
        for(int j = 1;j <= M;j ++)
            if(mp[i][j] == '.')
                return false;
    return true;
}


int main()
{
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= N;i ++)
        scanf("%s",mp[i] + 1);
    int t = 0;
    for(int i = 1;i <= N;i ++)
        for(int j = 1;j <= M;j ++)
            if(mp[i][j] == '.')
            {
                t ++;
                for(int k = 0;k < 4;k ++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x >= 1 && x <= N && y >= 1 && y <= M && mp[x][y] == '.')
                        du[i][j] ++;
                }
            }

    if(t & 1) {puts("Not unique"); return 0;}
    if(toposort())
    {
        for(int i = 1;i <= N;i ++,puts(""))
            for(int j = 1;j <= M;j ++)
                printf("%c",mp[i][j]);
    }
    else puts("Not unique");
    return 0;
}


L : gym - 100712H

给一个无向图,问加一条边最少剩下多少桥。

考虑缩点后的树:加一条边可以让树上的一条路径的桥全部去掉。剩下最少的桥,也就是去掉最多的桥,也就是让树上最长的一条路径去掉。这样就成了求树上最长链问题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;

LL read()
{
    char a = getchar();
    LL n = 0; bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int n,m,head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,id;
}l[SZ];

void build(int f,int t,int id)
{
    l[++ tot] = (edge){t,id};
    nxt[tot] = head[f];
    head[f] = tot;
}

int bcnt = 0,bri[SZ];
int dfn[SZ],low[SZ],dfs_clock = 0;

void tarjan(int u,int fa)
{
    dfn[u] = low[u]= ++ dfs_clock;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(fa == v) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u]) bcnt ++,bri[l[i].id] = 1;
        }
        else if(dfn[v] < dfn[u])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
}

int c[SZ];

void dfs(int u,int color)
{
    c[u] = color;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(!bri[l[i].id] && !c[v])
            dfs(v,color);
    }
}

int ff[SZ],tt[SZ],ccnt = 0;

queue<int> q;
int dist[SZ];
bool vis[SZ];
int bfs(int s,int flag)
{
    memset(dist,63,sizeof(dist));
    memset(vis,0,sizeof(vis));
    dist[s] = 0;
    q.push(s);
    while(q.size())
    {
        int u = q.front(); q.pop();
        vis[u] = 1;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(!vis[v])
                dist[v] = dist[u] + 1,vis[v] = 1,q.push(v);
        }
    }
    int maxn = -INF,u = 1;
    for(int i = 1;i <= ccnt;i ++)
        if(dist[i] > maxn)
            maxn = dist[i],u = i;
    if(flag == 0) return u;
    else return maxn;
}

void init()
{
    memset(head,0,sizeof(head)); tot = 1; ccnt = 0;
    memset(c,0,sizeof(c));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn)); dfs_clock = 0;
    memset(bri,0,sizeof(bri)); bcnt = 0;
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= m;i ++)
        {
            ff[i] = read(),tt[i] = read();
            build(ff[i],tt[i],i); build(tt[i],ff[i],i);
        }
        for(int i = 1;i <= n;i ++)
            if(!dfn[i])
                tarjan(i,0);
        for(int i = 1;i <= n;i ++)
            if(!c[i])
                dfs(i,++ ccnt);
    //    for(int i = 1;i <= n;i ++)    printf("%d ",c[i]); puts("");
        memset(head,0,sizeof(head)); tot = 1;
        for(int i = 1;i <= m;i ++)
            if(c[ff[i]] != c[tt[i]])
            {
                int u = c[ff[i]],v = c[tt[i]];
                build(u,v,1),build(v,u,1);
            }
        int s = bfs(1,0);
        int ans = bfs(s,1);
        printf("%d\n",ccnt - 1 - ans);
    }
    return 0;
}
/*
2
7 7
1 2
2 3
3 1
3 4
4 5
4 6
6 7

3 3
1 2
2 3
3 1


*/

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法tarjan图论拓扑排序模拟赛
最后由DQS修改于2017-08-08 21:07
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆