t1 徽章打洞：从每个起点a开始模拟，沿着p数组一步步走，每经过一个学生就记录一次，当某个学生第二次被经过时，他就是答案。每个起点都模拟一遍。

code

#include<bits/stdc++.h>
using namespace std;
int n,p[10005],cnt[10005];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>p[i];
    }
    for (int a=1;a<=n;a++) {
        memset(cnt,0,sizeof(cnt));
        int now=a;
        int ans;
        while(true) {
            cnt[now]++;
            if (cnt[now]==2) {
                ans=now;
                break;
            }
            now=p[now];
        }
        cout<<ans<<" ";
    }
    return 0;
}

t2 药剂合成：对每种药剂递归计算最小花费，若已拥有则花费为0，否则取直接购买和合成材料花费之和的较小值。遇到环时取直接购买的费用即可。

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,k;
long long cost[N];
vector<int> recipe[N];
long long dfs(int u){
    if(cost[u]==0) return 0;
    if(recipe[u].empty()) return cost[u];
    long long sum=0;
    for(int i=0;i<recipe[u].size();i++){
        sum += dfs(recipe[u][i]);
    }
    return min(cost[u], sum);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>cost[i];
            recipe[i].clear();
        }
        for(int i=1;i<=k;i++){
            int x;
            cin>>x;
            cost[x]=0;
        }
        for(int i=1;i<=n;i++){
            int m;
            cin>>m;
            for(int j=1;j<=m;j++){
                int x;
                cin>>x;
                recipe[i].push_back(x);
            }
        }
        for(int i=1;i<=n;i++){
            cout<<dfs(i)<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

t3 字母顺序：比较相邻两个名字，在第一个不同字符处建立大小关系，前者必须小于后者。若后者是前者的前缀则无解。建图后拓扑排序输出顺序，有环则无解。

#include<bits/stdc++.h>
using namespace std;
int n,in[1145],cnt,ans[1145];
string s1,s2;
vector<int>e[1145];
queue<int>q;
int main(){
    cin>>n;
    cin>>s1;
    for(int i=1;i<n;i++){
        cin>>s2; 
        int m=min(s1.size(),s2.size()),j;
        for(j=0;j<m;j++){
            if(s1[j]!=s2[j]){
                int x=s1[j]-96,y=s2[j]-96;
                e[x].push_back(y);
                in[y]++;
                break;
            }
        }
        if(j>=m&&s2.size()<s1.size()){
            cout<<"Impossible";
            return 0;
        }
        s1=s2;
    }
    for(int i=1;i<=26;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        ans[++cnt]=x;
        for(auto a:e[x]){
            in[a]--;
            if(!in[a]) q.push(a);
        }
    }
    if(cnt<26) cout<<"Impossible";
    else for(int i=1;i<=26;i++) cout<<(char)(ans[i]+96);
    return 0;
}

t4 捕鼠器：每个房间只能去往另一个固定房间，图由树指向环组成。对每个环单独考虑，在环上选一个费用最小的房间放捕鼠器，所有环的最小费用相加就是答案。

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2e5+20;
int n,m,cost[N],ans=0,k,to[N],du[N];
bool vis[N];
void Topo(int x){
	vis[x]=true;
	du[to[x]]--;
	if(!du[to[x]]) Topo(to[x]);
}
int Dfs(int x){
	vis[x]=true;
	if(!vis[to[x]]) return min(Dfs(to[x]),cost[x]);
	else return cost[x];
}
int main(){
	cin>>n;
	for(ri i=1;i<=n;i++) cin>>cost[i];
	for(ri i=1;i<=n;i++){
		int x;cin>>x;
		to[i]=x,du[x]++;
	}
	for(ri i=1;i<=n;i++) if(!du[i]&&!vis[i]) Topo(i);
	for(ri i=1;i<=n;i++) if(!vis[i]) ans+=Dfs(i);
	cout<<ans<<endl;
	return 0;
}

t5 最大路径权值：先判断图中是否有环，有环则路径可以无限长输出-1。无环则按顺序计算到达每个点时各字母累计出现的最大次数，取所有结果中的最大值

#include<bits/stdc++.h>
using namespace std;
int n,m,b[300005],in[300005],f[300005][26];
int ans,cnt,x,y;
string s;
vector<int> a[300005];
queue<int> q;
int main(){
    cin>>n>>m;
    cin>>s;
    for(int i=1;i<=n;i++) b[i]=s[i-1]-'a',f[i][b[i]]++;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        in[y]++;
        a[x].push_back(y);
    }
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
    while(q.size()){
        int k=q.front();
        q.pop();
        cnt++;
        for(int i=0;i<a[k].size();i++){
            int tmp=a[k][i];
            for(int j=0;j<26;j++){
                if(b[tmp]==j) f[tmp][j]=max(f[tmp][j],f[k][j]+1);
                else f[tmp][j]=max(f[tmp][j],f[k][j]);
            }
            in[tmp]--;
            if(!in[tmp]) q.push(tmp);
        }
    }
    if(cnt<n) cout<<"-1";
    else{
        for(int i=1;i<=n;i++){
            for(int j=0;j<26;j++) ans=max(ans,f[i][j]);
        }
        cout<<ans;
    }
    return 0;
}