2018年3月

Problem

请查看原题面。

Solution

参考的Solution:https://www.luogu.org/blog/user50971/solution-p3959

这题真的有点玄学。

状压是状压,但是记忆化搜索....没有体现利用了已经得到状态的过程。

也就是说记忆化搜索同样可以应用于剪枝。这应该算是一种剪枝类型的记忆化搜索,又或者是类SPFA-DFS顺序dp。

分析一下复杂度。 假设状态i转移到状态j,新增点x,需要枚举边(y,x)。y有n种情况。 可以转移到状态j的状态共有n种,因此状态j理论上最多被更新$n^2$次。 但若转移到状态j的状态再次被更新(非拓扑序dp可能遇见的情况),则状态j理论上最多被更新的次数$>n^2$。

所以综上,理论最优复杂度$O(n^32^n)$ -> $O(kn^32^n)$ -> $O(玄学/能过)$。

Code

// Code by ajcxsu
// Problem: Treasure

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

int n,m;
int E[13][13];
int f[1<<14];
int dis[13];
int U;

void dfs(int x) {
    if(x==U) return;
    for(int i=0;i<n;i++)
        if((1<<i)&x)
            for(int j=0;j<n;j++)
                if(E[i][j]!=INF && !((1<<j)&x))
                    if(f[x|(1<<j)] > E[i][j]*dis[i]+f[x]) {
                        int tmp=dis[j];
                        dis[j]=dis[i]+1;
                        f[x|(1<<j)]=E[i][j]*dis[i]+f[x];
                        dfs(x|(1<<j));
                        dis[j]=tmp;
                    }
}

int main() {
    memset(E,0x3f,sizeof(E));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    U=1<<n, U--;
    int u,v,w;
    for(int i=1;i<=m;i++) cin>>u>>v>>w, u--,v--, E[v][u]=E[u][v]=min(E[u][v],w);
    int ans=0x3f3f3f3f;
    for(int i=0;i<n;i++) {
        memset(f,0x3f,sizeof(f));
        memset(dis,0x3f,sizeof(dis));
        f[1<<i]=0, dis[i]=1;
        dfs(1<<i);
        ans=min(ans, f[U]);
    }
    cout<<ans<<endl;
    return 0;
}

Problem

小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家为点1,公司为点n,每条边长度均为一千米。小A想每天能醒地尽量晚,所以让你帮他算算,他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

Solution

本题操作有点骚。
对其进行可行性dp之后,我们再以得到的dp数组进行松弛。

令dp[i][j][k]代表点i跑2^k条边能到达的点。
然后得到这个数组跑个最短路就行。

数组的转移不难想,但不太好用式子表示。 加上Dijkstra,总体复杂度约是$O(64n^3)$,即约$O(n^4)$。

这个还有点难想到。我想的还比较久...但代码不难打233

Code

// Code by ajcxsu
// Problem: Running
#include<bits/stdc++.h>
using namespace std;

const int N=51,OP=64,M=1e4+10;
int n,m;
bool dp[N][OP][N];

int dijkstra(int s,int t) {
    int dist[N];
    bool S[N];
    memset(dist,0x3f,sizeof(dist)), memset(S,0,sizeof(S));
    dist[s]=0;
    for(int i=1;i<=n;i++) {
        int u=0;
        for(int j=1;j<=n;j++)
            if(!S[j] && dist[j]<dist[u]) u=j;
        S[u]=1;
        for(int j=0;j<OP;j++)
            for(int k=1;k<=n;k++)
                if(dp[u][j][k] && !S[k] && dist[k]>dist[u]+1)
                    dist[k]=dist[u]+1;
    }
    return dist[t];
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int u,v;
    for(int i=0;i<m;i++) cin>>u>>v, dp[u][0][v]=1;
    for(int j=1;j<OP;j++)
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++)
                if(dp[i][j-1][k])
                    for(int kk=1;kk<=n;kk++)
                        dp[i][j][kk]|=dp[k][j-1][kk];
    cout<<dijkstra(1,n)<<endl;
    return 0;
}

Problem

给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?

Solution

不再赘述。

传送门:https://www.cnblogs.com/ZegWe/p/6243883.html

感觉自己打得好傻逼...

Code

// Code by ajcxsu
// Problem: Network

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

const int N=1e5+10, M=3e4+10;
struct Edge {
    int u,v,w;
} e[M];
bool cmp(const Edge &a, const Edge &b) { return a.w<b.w; }
int n,m,q;

int f[N],l[N],r[N],fa[N],w[N],p;
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}

int siz[N],dep[N],son[N],idx;
int dfn[N],top[N];
void dfs1(int x,int k) {
    dep[x]=k, siz[x]=1;

    if(l[x]!=0) {
        dfs1(l[x],k+1);
        siz[x]+=siz[l[x]];
        if(siz[l[x]]>siz[son[x]]) son[x]=l[x];
    }
    if(r[x]!=0) {
        dfs1(r[x],k+1);
        siz[x]+=siz[r[x]];
        if(siz[r[x]]>siz[son[x]]) son[x]=r[x];
    }
}
void dfs2(int x,int t) {
    dfn[x]=++idx;
    top[x]=t;
    if(son[x]) dfs2(son[x],t);
    if(l[x]!=son[x] && l[x]) dfs2(l[x],l[x]);
    if(r[x]!=son[x] && r[x]) dfs2(r[x],r[x]);
}

int lca(int s,int t) {
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s,t);
        s=f[top[s]];
    }
    return dep[s]<dep[t]?s:t;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    p=n;
    for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++) {
        int u=e[i].u, v=e[i].v;
        int af=Find(u), bf=Find(v);
        if(af==bf) continue;
        l[++p]=af, r[p]=bf;
        f[af]=f[bf]=fa[af]=fa[bf]=p;
        w[p]=e[i].w;
    }
    dfs1(p,1);
    dfs2(p,p);
    int u,v;
    for(int i=0;i<q;i++) {
        cin>>u>>v;
        cout<<w[lca(u,v)]<<endl;
    }
    return 0;
}

Problem

有不知道多少个矿场,某个矿场可能塌陷。问最少在哪些矿场建逃生通道可以使某个矿场塌陷后每个矿场的旷工都能安全离开。

Solution

当某个点被断开以后这个图会变成不连通——也就是割点。于是你可以找到所有被割点分开的联通块,以割点相连,于是这就变成了像是缩点以后的一棵树。找到度数为1的点,第一个答案就是度数为1的点个数,第二个答案就是度数的积。

graph (2).png

比如如下这图(样例1),两个联通块:{3, 2, 5, 6} 和 {4},由1相连。
度数为1的联通块有两个。则需要在这两个联通块里面布置任意一个逃生通道就可以保证所有安全离开。因此总共的方案数为:4x1。

这个证明起来其实挺简单的。

graph (4).png

我们假设联通块最后缩成了这个样子(联通块之间的割点省略)。那么把(6,4)中间的割点给破坏掉,则我们可以发现,必须要在6中放置一个逃生通道,否则无法保证联通块6的安全。
因此我们首先得保证度数为1的联通块的安全。其次,度数不为一的点,破坏掉与它相连的任何一个割点,那么它总可以从另一个割点到达度数为1的联通块。因此这样的策略是正确的。

但是还有一个问题。假如没有割点。那么如果你只在这个联通块里放置一个逃生通道,是绝对有问题的。因为如果塌的是这个逃生通道,所有人都不能逃走。因此得至少放置两个逃生通道,而这两个逃生通道的位置是可以随便选的。因此若点数为$n$,特判方案数为$\frac {n(n-1)}{2}$。

Code

// Code by ajcxsu
// Problem: Mine

#include<bits/stdc++.h>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int N=1e3,M=2e3;
int h[N],to[M],nexp[M],p=1;
inline void ins(int a,int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

/* tarjan */
int dfn[N],low[N],idx,root;
int cut[N],col[N];
void tarjan(int x, int f) {
    dfn[x]=low[x]=++idx;
    int cnt=0;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            cnt++;
            tarjan(to[u], x);
            low[x]=min(low[x], low[to[u]]);
            if(low[to[u]]>=dfn[x] && f!=-1 && !cut[x]) cut[x]=1;
        }
        else if(to[u]!=f) low[x]=min(low[x], dfn[to[u]]);
    if(f==-1 && cnt>=2 && !cut[x]) cut[x]=1;
}

/* paint */
set<int> h2[N]; // 统计度数
int siz[N]; // 统计联通块大小
int cidx; // 统计联通块个数
void bfs(int s, int c) {
    queue<int> qu;
    qu.push(s);
    col[s]=c;
    while(!qu.empty()) {
        int na=qu.front();
        qu.pop();
        siz[c]++;
        for(int u=h[na];u;u=nexp[u])
            if(!cut[to[u]] && !col[to[u]]) col[to[u]]=c, qu.push(to[u]);
            else if(cut[to[u]]) h2[c].insert(to[u]);
    }
}

inline void init() {
    CLR(h), p=1, CLR(cut);
    CLR(siz), CLR(col), CLR(dfn), CLR(low), idx=0;
    for(int i=1;i<=cidx;i++) h2[i].clear();
    cidx=0;
}
int main() {
    ios::sync_with_stdio(false);
    int n,T=0;
    while(cin>>n, n) {
        init();
        int u,v;
        int na=0;
        for(int i=0;i<n;i++) cin>>u>>v, ins(u,v), ins(v,u), na=max(na,max(u,v));
        n=na;
        for(int i=1;i<=n;i++) if(!dfn[i]) root=i, tarjan(i, -1);
        for(int i=1;i<=n;i++) {
            if(!cut[i] && !col[i]) ++cidx, bfs(i, cidx);
        }
        long long ansa=0, ansb=1;
        for(int i=1;i<=cidx;i++)
            if(h2[i].size()<=1) ansa++, ansb*=siz[i];
        ++T;
        if(ansa==1) ansa=2, ansb=ansb*(ansb-1)/2;
        cout<<"Case "<<T<<": "<<ansa<<' '<<ansb<<endl;
    }
    return 0;
}