A：区间选点——（差分约束与spfa）

题目：

给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点

使用差分约束系统的解法解决这道题

输入：

输入第一行一个整数 n 表示区间的个数，接下来的 n 行，每一行两个用空格隔开的整数 a，b 表示区间的左右端点。1 <= n <= 50000， 0 <= ai <= bi <= 50000 并且 1 <= ci <= bi - ai+1。

输出：

输出一个整数表示最少选取的点的个数

输入样例：

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例：

6
首先说啥是差分约束，大概就是
一种特殊的 n 元一次不等式组，它包含 n个变量以及m个约束条件。
• 每个约束条件是由两个其中的变量做差构成的，形如𝑥i−𝑥j≤𝑐k， 其中𝑐k是常数（可以是非负数，也可以是负数）。
• 我们要解决的问题是：求一组解𝑥1=𝑎1,𝑥2=𝑎2,…,𝑥n=𝑎n，使 得所有的约束条件得到满足，否则判断出无解。
• 注意到，如果{𝑎1,𝑎2,𝑎3,…,𝑎n}是该差分约束系统的一组解，那么对 于任意的常数𝑑，显然{𝑎1+𝑑,𝑎2+𝑑,…,𝑎n+𝑑}也是该差分约束系统一组解。
求解差分约束系统，都可以转化为图论中得单源最短路问题
对于差分约束中的每一个不等式约束Xi-Xj<Ck,都可以移项变形为Xi<=Ck+Xj.如果令Ck=w(i,j) dis[i]=Xi,dis[j]=Xj ,那么原式变为dis[i]<=dis[j]+w(i,j),与最短路中的松弛操作相似。
由于原式为Xi<=Ck+Xj，求解是按照等于求解，跑最短路出来的最大解，如果想要最小解即为Xi>=Ck+Xj,跑最长路。

构造不等式组：
记sum[i]表示数轴上[0,i]之间选点的个数
对于第i个区间[ai,bi]需要满足sum[bi]-sum[ai-1]>=ci
同时需要保证sum[i]是有意义的，
0<=sum[i]-sum[i-1]<=1;
这时就会出现0<=sum[1]-sum[0]<=1; 此时为了方便整体后移改成sum[bi+1]-sum[ai]>=ci ； （可以后移也是基于差分约束系统+d,-d结果不变）
（以上内容搬运自某学长的PPT orz 侵删）
以上搞明白以后，这题就像是一个板子题了，用SPFA求单源最短路

#include <iostream>
#include <queue>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;
const int max1 = 1e8 * 5;
int m;
int head[1000000], dis[10000000], cnt[10001];
bool vis[100000];//, bl[10001];
//int al[1000000];
int max(int a, int b)
{
    if (a > b) return a;
    else return b;
}
struct edge
{
    int to;
    int next;
    int w;
};
int tot;
edge a[10000000];
void add(int x, int y, int w)
{
    a[++tot].to = y;
    a[tot].next = head[x];
    a[tot].w = w;
    head[x] = tot;
}
queue<int> q;
void SPFA()
{
    while (!q.empty()) q.pop();

    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= m; i++)
    {
        dis[i] = -max1;
    }
    dis[0] = 0;
    vis[0] = 1;
    q.push(0);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t]=0;
        for (int i = head[t]; i; i = a[i].next)
        {
            int y = a[i].to, w = a[i].w;
            if (dis[y] < dis[t] + w)
            {
                dis[y] = dis[t] + w;
                if (!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
}
int main()
{
    int n;
    int u, v, w;
    cin >> n;
    m = 0;
    memset(head, 0, sizeof(head));
    while(n--)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v + 1, w);
        m = max(m, v + 1);
    }
    for (int i = 1; i <= m; i++)
    {
        add(i, i - 1, -1);
        add(i - 1, i, 0); 
    }
    tot = 0;
        
    SPFA();

    cout << dis[m] << endl;
    return 0;
}

B：猫猫向前冲——（拓扑排序）

题目：

众所周知， TT 是一位重度爱猫人士，他有一只神奇的魔法猫。
有一天，TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫，编号依次为1，2，3，…，N进行比赛。比赛结束后，Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干。不幸的是，此时 TT 的电子设备遭到了宇宙射线的降智打击，一下子都连不上网了，自然也看不到最后的颁奖典礼。
不幸中的万幸，TT 的魔法猫将每场比赛的结果都记录了下来，现在他想编程序确定字典序最小的名次序列，请你帮帮他。

输入：

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示猫猫的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。

输出：

给出一个符合要求的排名。输出时猫猫的编号之间有空格，最后一名后面没有空格!

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

输入样例：

4 3
1 2
2 3
4 3

输出样例：

1 2 4 3

数据结构王老师举得拓扑排序的例子就是这个，拓扑排序本身思想比较简单。找一个入度为0的点。删去这个点和全部边。再找……
题目要求字典序最小。那正统的思路应该是用一个小根堆，每次把入度为零的全扔进去，取堆顶的点删去。
但我暴力居然过了。。。（没用小根堆优化）
我就放暴力的代码了（下次数据不一定善良，请优化）

#include<iostream>
#include<string.h>
using namespace std;
int mint(int a,int b)
{
    if(a>b) return b;
    else return a;
}
int head[1001]/*,vis1[1001]*/,vis[1001],dis1[1001],dis2[1001];
int father1[1001],father2[1001];
int min1(int a,int b)
{
    if(a>b) return b;
    else return a;
}
struct edge
{
    int to;
    int next;
};
int tot;
edge a[1000000];
void add(int x,int y)
{
    a[++tot].to=y;
    a[tot].next=head[x];
    head[x]=tot; 
}
int dil[1000000];
void quxiao(int t)
{
    for (int i = head[t]; i; i = a[i].next)
    {
        int y = a[i].to;
        dil[y]--;
    }
}
int main()
{
    int xulie[100000];
    
    int n,m;
    while(cin>>n)
    {
        memset(vis,0,sizeof(vis));
        memset(dil,0,sizeof(dil));
        memset(head,0,sizeof(head));
        cin>>m;
        for(int i=0;i<m;i++)
        {
            int u,v;
            cin>>u>>v;
            add(u,v);
            dil[v]++;
        }
        int w=0;
        int minc;
        while(w<n)
        {
            minc=1000000;
            for(int i=1;i<=n;i++)
            {
                if(!vis[i]&&dil[i]==0)
                {
                //  vis[i]=1;
                    minc=mint(minc,i);
                }
                
            }
            xulie[w]=minc;
            vis[minc]=1;
            quxiao(minc);
            w++;
        }
        for(int i=0;i<n;i++)
        {
            cout<<xulie[i];
            if(i!=n-1) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

C：班长竞选——（SCC 与缩点）

题目：

大学班级选班长，N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适 勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？

输入：

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。

输出：

对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！

输入样例：

2
4 3
3 2
2 0
2 1

3 3
1 0
2 1
0 2

输出样例：

Case 1: 2
0 1
Case 2: 2
0 1 2

这题就是，SCC+缩点
first，scc（找连通分量。）

image.png

（又不要脸的找来一堆资料,手打确实太麻烦）
其实就是两遍dfs的功夫。第一次确定（逆）后序序列，第二次把图返，然后确定每个点在哪个SCC里面。

第二部，缩点
缩点，每个SCC都作为一个点，连接SCC之间的线，得图G。此时存反图 fG。遍历点得到，每个 SCC中的详细的点。遍历边，然后寻找跨越不同SCC 中的边。
经分析可以知道，最大的票数应该在G 中指向SCC 最多的，但是这样计算不方便，因此用反图fG, 从出度为0的SCC 遍历，获取此SCC所能到达的所有SCC ，统计票数。

#include<iostream>
#include<vector>
#include <algorithm>
#include<string.h>
using namespace std;
const int N=5020;
int len;
int head1[5020],vis[5020];
vector<int> K1[5020],K2[5020],l[5020];
int ret[5020];
int num[5020];
int head2[5020];
struct edge
{
    int to;
    int next;
};
int tot1,tot2;
edge a[30010];
edge b[30010];
void add(int x,int y,edge *a,int *head,int &tot)
{
    a[++tot].to=y;
    a[tot].next=head[x];
    head[x]=tot; 
}
int n,f[N+1];
int dcnt=0,fcnt=0;
void dfs(int x,int *head)
{
    vis[x]=1;
    for (int i = head[x]; i; i = a[i].next)
    {
        int y=a[i].to;
        if(!vis[y])
        {
            dfs(y,head);
        }
    }
    f[x]=fcnt; fcnt++;
}
//int sccnum[5000];
int wk[5000+10];
int scc[5000+10];
int sccn=0;

void dfs2(int x,int &number)
{
    scc[x]=sccn;
    l[sccn].push_back(x);
    number++;
    vis[x]=1;
    for (int i = head2[x]; i; i = b[i].next)
    {
        int y=b[i].to;
        if(!vis[y])
        {
            dfs2(y,number);
        }
    }
}
void suodian()
{
    for(int x=0;x<n;x++)
    {
        for(int i=head1[x];i;i=a[i].next)
        {
            int y=a[i].to;
            if(scc[x]==scc[y])
                continue;
            K1[scc[x]].push_back(scc[y]);   
            K2[scc[y]].push_back(scc[x]);
        } 
    }
}

void dfs3(int x)
{
    vis[x]=1;
    len+=l[x].size();
    for(int i=0;i<K2[x].size();i++){
        if(!vis[K2[x][i]]){
            dfs3(K2[x][i]);
        }           
    }       
}

void solve(int *head)
{
    dcnt=0;fcnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        if(!vis[i]) dfs(i,head);
    }
}
void solve2()
{
    sccn=0;
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        int number=0;
        if(!vis[wk[i]]) dfs2(wk[i],number), sccn++;
        
    }
}
int main()
{
    int T;
    cin>>T;
    int w=1;
    while(T--)
    {
        tot1=0,tot2=0;
        //if(w!=1) cout<<endl;
        cout<<"Case "<<w<<": "; w++;
        cin>>n;
    
        memset(num,0,sizeof(num));
        memset(head1,0,sizeof(head1));
        memset(head2,0,sizeof(head2));
        int m;cin>>m;
        int u,v;
        while(m--)
        {
            cin>>u>>v;
            add(u,v,a,head1,tot1);
            add(v,u,b,head2,tot2);
        }
        solve(head1);
        for(int i=0;i<n;i++)
        {
            wk[n-1-f[i]]=i;
        }
    /*  for(int i=0;i<n;i++)
        {
            cout<<f[i]<<" ";
        }
        cout<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<wk[i]<<" ";
        }*/
        solve2();
        suodian();
        int maxans=0;
        
        for(int i=0;i<sccn;i++)
        {
            if(K1[i].size()==0)
            {
                for(int j=0;j<=sccn;j++)
                    vis[j]=0;
                len=0;
                dfs3(i);
                num[i]=len-1;
                maxans=max(maxans,num[i]);
            }
        }   
        cout<<maxans<<endl;
        int dss=0;
        for(int i=0;i<sccn;i++)
        {
            if(num[i]==maxans)
            {
                for(int j=0;j<l[i].size();j++)
                {
                    ret[dss]=l[i][j];
                    dss++;
                }
            }
        }
    //  dss--;
        sort(ret,ret+dss);
        for(int kdd=0;kdd<dss;kdd++)
        {
            cout<<ret[kdd];
            if(kdd!=dss-1) cout<<" ";
        }
        cout<<endl;
    /*  for(int i=0;i<sccn;i++)
        {
            cout<<"n"<<num[i]<<endl;
        }
        for(int i=0;i<n;i++)
        {
            cout<<scc[i]<<" ss";
        }
        cout<<endl;*/
    
    /*  for(int i=0;i<n;i++)
        {
            if(scc[i]==dl)
            {
                cout<<i<<" ";
            }
        }*/
        
        /*cout<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<f[i]<<" ";
        }
        cout<<endl;*/
        
        //cout<<"Case:"<<w<<" "; w++;
        for(int dssl=0;dssl<n;dssl++)
        {
            K1[dssl].clear();K2[dssl].clear();l[dssl].clear();
        }
    }
    return 0;
}