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（找连通分量。）
（又不要脸的找来一堆资料,手打确实太麻烦）
其实就是两遍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;
}
