HDU - 6041：I Curse Myself（Tarjan求环&K路归并）

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.

Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define V(k) V(k)

as the weight of the k k

-th smallest weighted spanning tree of this graph, however, V(k) V(k)

would be defined as zero if there did not exist k k

different weighted spanning trees.

Please calculate (∑ k=1 K k⋅V(k))mod2 32 (∑k=1Kk⋅V(k))mod232

InputThe input contains multiple test cases.

For each test case, the first line contains two positive integers n,m n,m

(2≤n≤1000,n−1≤m≤2n−3) (2≤n≤1000,n−1≤m≤2n−3)

, the number of nodes and the number of edges of this graph.

Each of the next m m

lines contains three positive integers x,y,z x,y,z

(1≤x,y≤n,1≤z≤10 6 ) (1≤x,y≤n,1≤z≤106)

, meaning an edge weighted z z

between node x x

and node y y

. There does not exist multi-edge or self-loop in this graph.

The last line contains a positive integer K K

(1≤K≤10 5 ) (1≤K≤105)

.OutputFor each test case, output " Case #x x

: y y

" in one line (without quotes), where x x

indicates the case number starting from 1 1

and y y

denotes the answer of corresponding case.Sample Input

Sample Output

Case #1: 6

Case #2: 26

Case #3: 493

题意：给一个仙人掌，求前K小的生成树的值之和。

思路：由于是仙人掌，即每个环去掉一条边才能得到生成树，那么就算每个环贡献一个数，求前K大。

每个集合贡献一个，求前K大我们可以用K路归并。从左到右两两合并，因为最后只要K个数，那么K以后的就不用保存了，所以每次合并最多保留K个数，则合并完的复杂度为O(NK)；

K路归并：当假设答案集合为A，新集合为B。那么对于B的每个数i，先把bi+a0放入大根堆里，然后开始操作：每次取队首X放入答案集合里，然后把对应的bi+a(j+1)又插入堆里，因为它是关于bi的最大的小于X的数，这样一直操作可以保证是最大的K个。（和“超级钢琴”那题一样，如果用了一个数X，我才把它分裂后的数（小于X）拿来考虑）。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn],Len[maxn],q[maxn],cnt;

int dfn[maxn],low[maxn],times,scc[maxn],scc_cnt,head,K;

vector<int>G[maxn];

struct in{

    int w,a,b;

    in(){}

    in(int ww,int aa,int bb):w(ww),a(aa),b(bb){}

    friend bool operator <(in x,in y){ return x.w<y.w;}

};

void add(int u,int v,int w){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;

}

void tarjan(int u,int fa)

{

    dfn[u]=low[u]=++times;

    q[++head]=u;

    for(int i=Laxt[u];i;i=Next[i]){

        if(To[i]==fa) continue;

        if(!dfn[To[i]]) {

              tarjan(To[i],u);

              low[u]=min(low[u],low[To[i]]);

        }

        else low[u]=min(low[u],dfn[To[i]]);

    }

    if(low[u]==dfn[u]){

        scc_cnt++;

        while(true){

            int x=q[head--];

            scc[x]=scc_cnt;

            if(x==u) break;

        }

    }

}

void merge(vector<int>&a,vector<int>b){

    vector<int>res;

    priority_queue<in>q;

    for(int i=;i<b.size();i++)

      q.push(in(a[]+b[i],,i));

    while(res.size()<K&&!q.empty()){

        in it=q.top(); q.pop();

        res.push_back(it.w);

        if(it.a+<a.size()){

            it.a++;     //当前数没了就把当前数的次大值拉进来，ok。

            q.push(in(a[it.a]+b[it.b],it.a,it.b));

        }

    }

    a=res;

}

int main()

{

    int N,M,u,v,w,C=,sum; unsigned int res;

    while(~scanf("%d%d",&N,&M)){

        rep(i,,N) Laxt[i]=dfn[i]=scc[i]=low[i]=;

        cnt=times=scc_cnt=head=; sum=; res=;

        rep(i,,M) {

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w); add(v,u,w); sum+=w;

        }

        tarjan(,);

        rep(i,,scc_cnt) G[i].clear();

        rep(i,,N)

          for(int j=Laxt[i];j;j=Next[j])

            if(To[j]>i&&scc[i]==scc[To[j]])

              G[scc[i]].push_back(Len[j]);

        scanf("%d",&K);

        vector<int>ans; ans.push_back();

        rep(i,,scc_cnt){

            if(G[i].size()>) merge(ans,G[i]);

        }

        for(int i=;i<ans.size();i++) res+=(i+)*(sum-ans[i]);

        printf("Case #%d: %u\n",++C,res);

    }

    return ;

}

无向图tarjan：按边存。(想象一下有的点存在于多个环里)

void tarjan(int u,int fa)

{

    dfn[u]=low[u]=++times; vis[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        int v=To[i];

        if(!F[i]) continue;

        F[i]=F[i^]=;

        if(!vis[v]){

            q[++head]=i;

            tarjan(v,u);

            low[u]=min(low[u],low[v]);

            if(dfn[u]<=low[v])

            {

                int k,fcy=; scc_cnt++;

                do

                {

                    k=q[head--];

                    fcy++;

                    scc[k]=scc_cnt;

                } while (k!=i);

                if(fcy>) ans1++,ans2=(ll)ans2*(fcy+)%Mod;;

            }

        }

        else if(dfn[v]<dfn[u]){

            q[++head]=i;

            low[u]=min(low[u],dfn[v]);

        }

    }

}

裸题K路归并：POJ2442，M个集合，每个集合大小为N，每个集合选一个数加起来，问前N小。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

struct in{

    int x,pos;

    in(){}

    in(int xx,int pp):x(xx),pos(pp){}

    friend bool operator <(in w,in v){return w.x>v.x;}

};

void merge(vector<int>&G,int N)

{

    vector<int>res; priority_queue<in>q;

    for(int i=,x;i<=N;i++){

        scanf("%d",&x);

        q.push(in(G[]+x,));

    }

    while(!q.empty()&&res.size()<N){

        in w=q.top(); q.pop();

        res.push_back(w.x);

        if(w.pos+<G.size())

            q.push(in(w.x+G[w.pos+]-G[w.pos],w.pos+));

    }

    G=res;

}

int main()

{

    int T,M,N;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&M,&N);

        vector<int>G ;

        G.push_back();

        for(int i=;i<=M;i++) merge(G,N);

        for(int i=;i<N;i++) printf("%d ",G[i]);

        puts("");

    }

    return ;

}

巴特西

HDU - 6041：I Curse Myself（Tarjan求环&K路归并）

最新文章

热门文章