算法周周练7

（EAD）

E：数字比较

思路：x,y范围都是1e9，而且还是计算次方，直接计算肯定是不行的。根据高中数学知识，可以两边同时取对数，就化成了比较ylogx和xlogy的大小。

代码：

///ylogx和xlogy
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    ll x,y;
    cin>>x>>y;
    ll a=y*log(x);
    ll b=x*log(y);
    if(a==b) puts("=");
    else if(a>b) puts(">");
    else puts("<");
    return 0;
}

A：收集纸片

思路：因为数据范围很小所以可以考虑暴力枚举出收集纸片的顺序，取min即可。可以用dfs，C++里STL的next_permutation函数，状压DP应该也可。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

PII a[20];
int b[20];

int main(){
    int t;cin>>t;
    while(t--){
        int n,m,sx,sy;
        cin>>n>>m;
        cin>>sx>>sy;
        int k;cin>>k;
        for(int i=1;i<=k;i++){
            int x,y;
            cin>>x>>y;
            a[i]={x,y};
            b[i]=i;
        }
         int res=0x3f3f3f3f;
    do{
        int lx=sx,ly=sy;
        int sum=0;
        for(int i=1;i<=k;i++){
            sum+=abs(lx-a[b[i]].first)+abs(ly-a[b[i]].second);
            lx=a[b[i]].first,ly=a[b[i]].second;
        }
        res=min(res,sum+abs(lx-sx)+abs(ly-sy));
    }while(next_permutation(b+1,b+1+k));

    printf("The shortest path has length %d\n",res);
    }


    return 0;
}

D：华华和月月逛公园

题意：给定一个无向连通图，求走过所有点不需要走过的边的数量。

思路：无向图里保持连通必须要经过的边叫做桥，用总边数减去桥的个数就是答案。所以问题就转化成了如何求无向图连通图里桥的个数。

桥的概念，桥是指的无向图里的一条无向边，删去该边后连通图将不再连通。

对每个点定义两个时间戳
dfn[u]遍历到u的时间
low[u]表示从u开始走 所能遍历到的最小时间戳

如何找到桥：x->y的祖先节点 x->y不是桥

桥<==>dfn[x]<low[y]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100,maxm=maxn*6;

int h[maxn],dfn[maxn],low[maxn];
int e[maxm],ne[maxm],idx;
int timetmp=0;
int res=0;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int fa){
    low[u]=dfn[u]=++timetmp;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        if(!dfn[j]){
            tarjan(j,u);
            low[u]=min(low[u],low[j]);
            if(low[j]>dfn[u]) res++;
        }
        else low[u]=min(low[u],dfn[j]);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);add(y,x);
    }
    tarjan(1,0);
    cout<<m-res<<endl;
    return 0;
}

C：觉得写的很好的题解