长乐Day？.2

————补一下昨天的

体验了一下MARKDOWN，发出来的和预览的效果有些不一样，为了解决这个问题，部分用图片代替。

最短路

T1:

T2：

看完题解，斯坦纳树，现学吧。看了一下OIWIKI的，有点像费马点。好个数形结合，明天再来。

斯坦纳树-OIWIKI

T3：

把图变成有向图，把环分成三部分，化为单源+单汇来求解，还没调出来。

强连通分量

以为很难实际上算比较简单的。

T1：

不难发现一条链上的点不能同时染色，于是就变成求最长连，Tarjan缩点+拓扑排序搞定。

#include
#define N 10001
using namespace std;
int n,m,ans;
int cnt,tim,low[N],col[N],dfn[N],sum[N];
int inn[N],dp[N];
vectorEdge[N],edge[N];
stacks;
queueq;
void Tarjan(int u)
{
    low[u]=dfn[u]=++tim;
    s.push(u);
    for(int i=0;i>n>>m; 
    int a,b;
    for(int i=1;i>a>>b;
        Edge[a].push_back(b);
    }

    for(int i=1;i<=n;i++) 
    {
        if(!dfn[i]) Tarjan(i);
    }
    for(int u=1;u<=n;u++)
    {
        for(int i=0;i<Edge[u].size();i++)
        {
            int v=Edge[u][i];
            if(col[u]!=col[v])
            {
                edge[col[u]].push_back(col[v]);
                inn[col[v]]++;
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        if(!inn[i])
        {
            q.push(i);
            dp[i]=sum[i];
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<edge[u].size();i++)
        {
            int v=edge[u][i];
            dp[v]=max(dp[v],dp[u]+sum[v]);
            inn[v]--;
            if(!inn[v]) q.push(v);
        }
    }
    for(int i=1;i<=cnt;i++) ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

T2：

依题，可以经过一个点或边无数次，所以先缩点，然后就是求从市中心开始到某个酒吧结束的最长路径，用SPFA求最长路径来做。

#include
#define N 500001
using namespace std;
int n,m,ss,p,f,ans;
int cnt,tim,dis[N],w[N],low[N],col[N],dfn[N],sum[N];
bool vis[N],Bar[N];
vectorEdge[N],edge[N],bar;
stacks;
queueq;
void Tarjan(int u)
{
    low[u]=dfn[u]=++tim;
    s.push(u);
    for(int i=0;idis[i])
            {
                dis[i]=dis[t]+sum[i];
                if(!vis[i])
                {
                    vis[i]=true;
                    q.push(i);
                }
            }
        }
    }
}
int main()
{
    freopen("plan.in","r",stdin);
    freopen("plan.out","w",stdout);
    cin>>n>>m; 
    int a,b;
    for(int i=1;i>a>>b;
        Edge[a].push_back(b);
    }
    for(int i=1;i>w[i];
    }
    cin>>ss>>p;
    for(int i=1;i>a;
        Bar[a]=true;
    }

    for(int i=1;i<=n;i++) 
    {
        if(!dfn[i]) Tarjan(i);
    }
    for(int u=1;u<=n;u++)
    {
        for(int i=0;i<Edge[u].size();i++)
        {
            int v=Edge[u][i];
            if(col[u]!=col[v])
            {
                edge[col[u]].push_back(col[v]);
            }
        }
    }
    SPFA(f);
    for(auto i:bar)
    {
        ans=max(ans,dis[i]);
    }
    cout<<ans;
    return 0;
}

试用了一下auto，和原版没啥差别，要开C++11，小心!。

T3：

太晚了，明天再来。

算是难度比较低的一天。