牛客算法周周练7(ADE)

A:收集纸片
思路：注意到n非常小，所以我们可以考虑暴力。枚举一个全排列计算最小距离就好~
代码：

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

const int maxn = 100;
pair<int,int>ans[maxn];
const int inf = 0x3f3f3f3f;
bool vis[maxn]={false};
int res = 0;
int p,x,y;
int getdis(int x,int y,int x1,int y1){
    return abs(x-x1)+abs(y-y1);
}
void dfs(int n,int fx,int fy,int len){
    if(n == p){
        len += getdis(x,y,fx,fy);
        if(len < res) res = len;
        return ; 
    }
    for(int i=1;i<=p;i++){
        if(vis[i])continue;
        vis[i] = true;
        dfs(n+1,ans[i].first,ans[i].second,len + getdis(fx,fy,ans[i].first,ans[i].second));
        vis[i] = false;
    }
}
int main(){
    int t;cin>>t;
    while(t--){
        res = inf;
        memset(vis,false,sizeof(vis));
        int n,m;cin>>n>>m;
        cin>>x>>y;
        cin>>p;
        for(int i=1;i<=p;i++){
            cin>>ans[i].first>>ans[i].second;
        }
        dfs(0,x,y,0);
        cout<< "The shortest path has length "<<res<<endl;
    }
}

D:华华和月月逛公园
思路：这题其实也很简单，要我们求的是哪些边可以删掉，仍然保持连通性，换个角度想就是图中有多少个桥，然后用总的边数-桥的数量，剩下的全部可以删掉任然有连通性，这个题考察的算法就是tarjan算法求桥，虽然我不会但是我百度个板子一样过(奥里给~),赛后补了一下Tarjan算法。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
struct edge{
    int v,next;
    edge(){}
    edge(int a,int c):v(a),next(c){}
}e[maxn << 1];
int head[maxn << 1],tot;
void add(int u,int v){
    e[++tot].v = v;
    e[tot].next = head[u];
    head[u] = tot;
}
int dfn[maxn << 1],low[maxn << 1],cnt;
int ti = 0;
void tanjan(int u,int fu){
    dfn[u] = low[u] = ++ti;
    for(int i = head[u]; i ; i = e[i].next){
        int v = e[i].v;
        if(!dfn[v]){
            tanjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u])
                cnt++;
        }else if(v != fu){
            low[u] = min(low[u],low[v]);
        }
    }
}
void solved(){
    int n,m;cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int u,v;cin>>u>>v;add(u,v);add(v,u);
    }
    tanjan(1,1);
    cout<<m - cnt<<endl;
}
int main(){
    solved();
    return 0;
} 

E:数字比较
思路：


然后判断一下就好了~
代码：

#include<bits/stdc++.h>
using namespace std;

void solved(){
    int x,y;cin>>x>>y;
    double a = y * log(x),b = x * log(y);
    if(a > b)cout<<">"<<endl;
    else if(a < b)cout<<"<"<<endl;
    else cout<<"="<<endl; 
}
int main(){
    solved();
    return 0;
}