2022.2.13 学习总结

（1）.[USACO08OPEN]Clear And Present Danger S - 洛谷

FLOYD算法模板题。

#include
#include
using namespace std;
int dis[1000][1000],order[1000100];
int main()
{
    int n,m,i,j,k,sum=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    cin>>order[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        cin >> dis[i][j];
    for(k = 1; k <= n; k++)
    for(i = 1; i <= n; i++)
    for(j = 1; j <= n; j++)
    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    sum = dis[1][order[1]];
    for(i = 2; i <= m; i++) sum += dis[order[i - 1]][order[i]];
    sum += dis[order[m]][n];
    cout << sum< 
题目要求行经路径中包含指定路径，那么在使用floyd算法更新完所有最短路径后，再用循环加上“走过指定路径”的危险度，就可以得到答案了。
 
（2）.炸铁路 - 洛谷
 
这题似乎与我们现在学的知识点没什么太大的关系，不用最短路的算法。我用的并查集算法。
 
由于题目说最终的输出答案须要按照a的大小顺序输出，如果a相同就按b的大小顺序，而且如果a>b就要交换顺序。
 
所以我们在输入时先保证左边的值一定小于右边的值，输入完后再重新排序一遍。
 
而后就是逐个遍历，去掉某条路线时再将其它路线利用并查集链接，检查是否会出现“无法到达某个城市”的情况，如果出现那么就说明这条路线符合题目要求
 
#include
using namespace std;
int n,m,fla,parent[10001],flag;
struct abc{
int a,b;
}ans[20000];
bool cmp(abc a,abc b)
{
    if(a.a>ans[i].a>>ans[i].b;
    if(ans[i].a>ans[i].b)swap(ans[i].a,ans[i].b);
    }
    sort(ans+1,ans+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        flag=0;
        for(int j=1;j<=n;j++)parent[j]=j;
        for(int j=1;j<=m;j++)
        if(i != j) unionn(ans[j].a,ans[j].b);
        if(flag != n-1)printf("%d %dn",ans[i].a,ans[i].b);
    }
    return 0;
}