P2835 刻录光盘

分析各个数组的作用:
dfn:该点第几次被遍历到
low:该点及其子树最早被遍历到的次序号。
inq:改点是否在栈中
bl:改点属于第几个强连通分量
sz:该强连通分量中包含几个点
in:强连通分量中的入读关系，若为0则说明该分量并没有被其他分量指向。

#include <bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int head[N],nxt[N],v[N],n,cnt,ans;
int dfn[N],low[N],inq[N],ti,tol,bl[N],sz[N],in[N];
stack<int>q;
void add(int from,int to)
{
    v[++cnt]=to;
    nxt[cnt]=head[from];
    head[from]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++ti;
    q.push(u);
    inq[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int j=v[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(inq[j])
            low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        tol++;int tmp;
        do
        {
            tmp=q.top();q.pop();
            inq[tmp]=0;
            bl[tmp]=tol;sz[tol]++;
        }while(tmp!=u);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        while(cin>>x&&x)
            add(i,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int u=1;u<=n;u++)
    {
        for(int i=head[u];i;i=nxt[i])
        {
            int j=v[i];
            if(bl[u]!=bl[j])
                in[bl[j]]++;
        }
    }
    for(int i=1;i<=tol;i++)
        if(!in[i]) ans++;
    cout<<ans<<endl;
    return 0;
}

P2941 [USACO09FEB]Surround the Islands S

利用tarjan算法得出每个点属于哪个强连通分量。
利用处理好的岛屿建图，岛屿间的最短距离为两岛之中两个点的最短距离；
由于任何一个点都可以到达另外一个岛屿上的某个点，不必关心出度和入读；
双重for循环，暴力判断最小值。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int head[N],nxt[N],v[N],n,cnt,ans,cost[505][505],mi=inf;
int dfn[N],low[N],inq[N],ti,tol,bl[N],sz[N],in[N];
stack<int>q;
void add(int from,int to)
{
    v[++cnt]=to;
    nxt[cnt]=head[from];
    head[from]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++ti;
    q.push(u);
    inq[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int j=v[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(inq[j])
            low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        tol++;int tmp;
        do
        {
            tmp=q.top();q.pop();
            inq[tmp]=0;
            bl[tmp]=tol;sz[tol]++;
        }while(tmp!=u);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    memset(cost,inf,sizeof(cost));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;cin>>x;
            cost[bl[i]][bl[j]]=min(cost[bl[i]][bl[j]],2*x);
        }
    for(int i=1;i<=tol;i++)
    {
        for(int j=1;j<=tol;j++)
            ans+=cost[i][j];
        mi=min(mi,ans);
        ans=0;
    }
    cout<<mi<<endl;

    return 0;
}

P2237 [USACO14FEB]Auto-complete S

1.对字符串进行排序。sort默认对first排序，当first相等时，根据second排序。
2.使用pair容器，记录输入时的位置。
3.lowerbound可对字符串数组使用，取子串利用string类型substr方法

#include <bits/stdc++.h>

using namespace std;
const int N=3e4+5;
int w,n;
pair<string,int>a[N];
bool check(string s1,string s2)
{
    if(s1.length()<s2.length()) return 0;
    string tmp=s1.substr(0,s2.length());
    if(tmp!=s2) return 0;
    return 1;
}
int main()
{
    cin>>w>>n;
    for(int i=1;i<=w;i++)
        cin>>a[i].first,a[i].second=i;
    sort(a+1,a+w+1);
    //pair 默认对first升序，当first相同时对second升序；
    while(n--)
    {
        int k;string ss;
        cin>>k>>ss;
        int g=lower_bound(a+1,a+w+1,make_pair(ss,0))-a;
        g+=k-1;
        if(g>w||!check(a[g].first,ss))
            cout<<-1<<endl;
        else
            cout<<a[g].second<<endl;
    }
    return 0;
}

P3119 [USACO15JAN]Grass Cownoisseur G

真麻烦，好久没打这种题了，虽然是个紫题，但也写了好久

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int head[N],nxt[N],v[N],cnt;
int head1[N],nxt1[N],v1[N],c1,dis1[N];
int head2[N],nxt2[N],v2[N],c2,dis2[N];
int n,m,ans,mx;
int dfn[N],low[N],inq[N],ti,tol,bl[N],sz[N],st;
bool vis[N],used[N];
stack<int>q;
void add(int from,int to) {v[++cnt]=to;nxt[cnt]=head[from];head[from]=cnt;}
void add1(int from,int to) {v1[++c1]=to;nxt1[c1]=head1[from];head1[from]=c1;}
void add2(int from,int to) {v2[++c2]=to;nxt2[c2]=head2[from];head2[from]=c2;}
void tarjan(int u)
{
    dfn[u]=low[u]=++ti;
    q.push(u);
    inq[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int j=v[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(inq[j])
            low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        tol++;int tmp;
        do
        {
            tmp=q.top();q.pop();
            inq[tmp]=0;
            bl[tmp]=tol;sz[tol]++;
        }while(tmp!=u);
    }
}
void spfa1(int u)
{
    dis1[u]=sz[u];
    queue<int>q;q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
        int cur=q.front();q.pop();
        vis[cur]=0;
        for(int i=head1[cur];i;i=nxt1[i])
        {
            int j=v1[i];
            if(dis1[j]<dis1[cur]+sz[j])
            {
                dis1[j]=dis1[cur]+sz[j];
                if(!vis[j])
                    q.push(j),vis[j]=1;
            }
        }
    }
}
void spfa2(int u)
{
    //memset(vis,0,sizeof(vis));
    dis2[u]=sz[u];
    queue<int>q;q.push(u);
    vis[u]=1;
    while(!q.empty())
    {
        int cur=q.front();q.pop();
        vis[cur]=0;
        for(int i=head2[cur];i;i=nxt2[i])
        {
            int j=v2[i];
            if(dis2[j]<dis2[cur]+sz[j])
            {
                dis2[j]=dis2[cur]+sz[j];
                if(!vis[j])
                    q.push(j),vis[j]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
    {
        for(int u=head[i];u;u=nxt[u])
        {
            if(bl[i]!=bl[v[u]])
                add1(bl[i],bl[v[u]]),add2(bl[v[u]],bl[i]);
        }
    }
    st=bl[1];
    spfa1(st);spfa2(st);
    for(int i=1;i<=n;i++)
    {
        if(!used[bl[i]]&&dis1[bl[i]])
        {
            int now=bl[i];
            used[now]=1;
            for(int g=head2[now];g;g=nxt2[g])
            {
                int j=v2[g];
                if(!dis2[j]) continue;
                mx=max(mx,dis1[now]+dis2[j]-sz[st]);
            }
        }
    }
    cout<<mx<<endl;
    return 0;
}