Tarjan可以把非DAG转化成DAG

懵逼的 题目

BZOJ 1179

扯淡的 题解

是抱着刷Tarjan的觉悟来写这道题的…
乍一看不就是个裸的缩点×DAG嘛 (flag)
然后发现忘了Tarjan怎么打了

打出Tarjan, 不会DAG上的DP 写了个DFS, 结果TTT

改成DP (其实就是个BFS) , 结果TTT

然后记录当前节点是不是已经在队列里了…结果就A了?????
行吧…权当是个新优化吧…

沙茶的 代码

// bzoj1179.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (500000 + 5)
#define MAXM (500000 + 5)
int s;
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
}b[MAXM << 1], bn[MAXM << 1];
int cntb = 0, cntn = 0;
int g[MAXN], gn[MAXN];

int cntd = 0;
int dfn[MAXN];
int low[MAXN];
stack<int> ts;
bool instack[MAXN];

int fa[MAXN];

int nn, nm;
int nbarn;
int nmon[MAXN];
bool nbar[MAXN];


int n, m;
int barn;
int mon[MAXN];
bool bar[MAXN];

int ans = 0;
int dans[MAXN];

void tarjan(int);
void dp();
void init();
void inite();
void adn(int, int);
void adnn(int, int);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            tarjan(i);
        }
    }
    inite();
    dp();
    cout << ans;
    return 0;
}

void init()
{
    memset(instack, false, sizeof(instack));
    memset(bar, false, sizeof(bar));
    memset(mon, 0, sizeof(mon));
    cin >> n >> m;
    int srx, sry;
    for (int i = 1; i <= m; i++)
    {
        cin >> srx >> sry;
        adn(srx, sry);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> mon[i];
    }
    cin >> s >> barn;
    for (int i = 1; i <= barn; i++)
    {
        cin >> srx;
        bar[srx] = true;
    }
}

void tarjan(int dq)
{
    low[dq] = dfn[dq] = ++cntd;
    ts.push(dq);
    instack[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (!dfn[b[i].to])
        {
            tarjan(b[i].to);
            low[dq] = min(low[dq], low[b[i].to]);
        }
        else if (instack[b[i].to])
        {
            low[dq] = min(low[dq], dfn[b[i].to]);
        }
    }
    if (low[dq] == dfn[dq])
    {
        while (ts.top() != dq)
        {
            fa[ts.top()] = dq;
            instack[ts.top()] = false;
            ts.pop();
        }
        fa[dq] = dq;
        instack[ts.top()] = false;
        ts.pop();
    }
}

void inite()
{
    for (int i = 1; i <= m; i++)
    {
        if (fa[b[i].from] != fa[b[i].to])
        {
            nm++;
            adnn(fa[b[i].from], fa[b[i].to]);
        }    
    }
    for (int i = 1; i <= n; i++)
    {
        if (bar[i])
        {
            nbar[fa[i]] = true;    
        }
        nmon[fa[i]] += mon[i];
    }
}

void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}

void adnn(int from, int to)
{
    bn[++cntn].next = gn[from];
    bn[cntn].from = from;
    bn[cntn].to = to;
    gn[from] = cntn;
}

void dp()
{
    queue<int> q;
    q.push(fa[s]);
    dans[fa[s]] = nmon[fa[s]];
    bool v[MAXN];
    memset(v, false, sizeof(v));
    while(!q.empty())
    {
        int dq = q.front();
        v[dq] = false;
        q.pop();
        if (nbar[dq])
        {
            ans = max(ans, dans[dq]);
        }
        for (int i = gn[dq]; i; i = bn[i].next)
        {
            if (dans[bn[i].to] < dans[dq] + nmon[bn[i].to])
            {
                dans[bn[i].to] = max(dans[bn[i].to], dans[dq] + nmon[bn[i].to]);
                if (!v[bn[i].to])
                {
                    q.push(bn[i].to);
                    v[bn[i].to] = true;
                }

            }

        }
    }
}

/*
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1
5
1 4
4
3
5
6
*/

By 不会Tarjan初赛药丸的 Cansult