HDU 6081度クマの王国戦略スタック最適化Stoer-Wagnerアルゴリズム

タイトル:
http://acm.hdu.edu.cn/showproblem.php?pid=6081
タイトル:
Problem Description度度熊国王はニャーハッ族の勇士を率いて、ジャラ族を攻撃しようとした.ガチャガチャ族は強い民族で、知恵に満ちた謀士がいて、無限の力を持つ戦士がいます.だからこの戦争は、非常に困難になるだろう.より良い攻撃のためにガチャガチャ族、度度度熊はまず内部からガチャガチャ族を瓦解すべきだと決めた.最初のステップは、ガチャガチャ族の内部が同心で力を合わせることができず、内部に隙間が必要になることです.ガチャガチャ族には全部でn人の将軍がいて、彼らは全部でm人の強い関係を持っていて、すべての強い関係を破壊するには一定の代価が必要です.今度熊はあなたにいくつかの強い関係を破壊する必要があることを命令して、内部の将軍は、これらの強い関係を通じて、完全な連通ブロックにつながって、戦争の順調な進行を保証することはできません.すみません、最低いくらの代価を払うべきですか?
考え方:
問題の意味から見ると、明らかにグローバル最小割であるが、データのため、水を流すことができ、スタック最適化stor-wagnerアルゴリズムテンプレートを貼り、記録することができる.コード参照:http://www.cnblogs.com/oyking/p/7340753.html

//   (nmlogm)，       ，              
//    1  
#include 

using namespace std;

typedef pair<int, int> pii;
const int N = 3000 + 10, M = 20000 + 10, INF = 0x3f3f3f3f;

struct edge
{
    int to, cost, next;
}g[M];

int cnt, head[N], link[N];//link     
int par[N];
int dis[N];//dis         A               
bool vis[N];//           A    
void init(int n)
{
    for(int i = 1; i <= n; i++) par[i] = i;
}
void add_edge(int v, int u, int cost)
{
    g[cnt].to = u, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
}
int ser(int x)
{
    int r = x, i = x, j;
    while(r != par[r]) r = par[r];
    while(par[i] != r) j = par[i], par[i] = r, i = j;
    return r;
}
void unite(int x, int y)
{// y   x ，     
    int p = x;
    while(~ link[p]) p = link[p];
    link[p] = y;
    par[y] = x;
}
int min_cut_phase(int n, int &s, int &t)
{
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    priority_queue que;
    t = 1;
    while(--n)
    {
        vis[s = t] = true;
        for(int i = s; ~i; i = link[i])//  dis  ，    s        
            for(int j = head[i]; ~j; j = g[j].next)
            {
                int v = ser(g[j].to);//g[j].to            
                if(! vis[v]) que.push(make_pair(dis[v] += g[j].cost, v));
            }
        t = 0;
        while(! t)
        {
            if(que.empty()) return 0; //    
            pii p = que.top(); que.pop();
            if(dis[p.second] == p.first) t = p.second;
        }
    }
    return dis[t];
}
int stoer_wagner(int n)
{
    int ans = INF, s, t;
    for(int i = n; i > 1; i--)
    {
        ans = min(ans, min_cut_phase(i, s, t));
        if(ans == 0) break;
        unite(s, t);
    }
    return ans;
}
int main()
{
    int n, m;
    while(~ scanf("%d%d", &n, &m))
    {
        init(n);
        cnt = 0;
        memset(head, -1, sizeof head);
        memset(link, -1, sizeof link);
        int a, b, c;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            add_edge(a, b, c), add_edge(b, a, c);
        }
        printf("%d
", stoer_wagner(n));
    }
    return 0;
}

別のテンプレート(理解できません):

#include 
//#include 
#define rep(i,n) for(int i=1;i<=n;++i)
#define inf 0x3f3f3f3f
#define M 100005
#define N 3005
using namespace std;
//__gnu_pbds::priority_queue q;

struct Eedge
{
    int x,y,w;
} e[M];
struct edge
{
    int v,c,f;
} ee[2][M];
struct node
{
    int len,pos;
};
int operator const node &a,const node &b)
{
    return a.lenint cmp(Eedge x,Eedge y)
{
    if(x.x==y.x)return x.yreturn x.xint b[2][N],d[N];
priority_queue q;
int n,m,ans,x,y,z,tot[2],top,tp,ts,tr;
bool f[N],r;
int tab[N];
void adds(bool p,int x,int y,int w)
{
    ee[p][++tot[p]]=(edge)
    {
        y,w,b[p][x]
    };
    b[p][x]=tot[p];
}
void add(bool p,int x,int y,int w)
{
    adds(p,x,y,w);
    adds(p,y,x,w);
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(b,0,sizeof b);
        tot[0]=tot[1]=0;
        ans=inf;
        rep(i,m)
        {
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
            if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
        }
        sort(e+1,e+m+1,cmp);
        top=0;
        rep(i,m)if(e[top].x!=e[i].x||e[top].y!=e[i].y)e[++top]=e[i];
        else e[top].w+=e[i].w;
        m=top;
        rep(i,m)if(e[i].x!=e[i].y)add(0,e[i].x,e[i].y,e[i].w);
        r=0;
        rep(zz,min(n-1,max(400,n/2-1)))
        {
            memset(d,0,sizeof d);
            memset(f,0,sizeof f);
            d[1]=inf;
            q.push((node)
            {
                d[1],1
            });
            tp=0;
            while(!q.empty())
            {
                x=q.top().pos;
                q.pop();
                if(f[x])continue;
                for(int i=b[r][x]; i; i=ee[r][i].f)
                {
                    int v=ee[r][i].v;
                    if(!f[v])d[v]+=ee[r][i].c,q.push((node){d[v],v});
                }
                f[x]=1;
                ++tp;
                if(tp==n-zz+1)ts=x;
                if(tp==n-zz)tr=x;
            }
            tp=0;
            for(int i=b[r][ts]; i; i=ee[r][i].f)tp+=ee[r][i].c;
            r^=1;
            ans=min(ans,tp);
            memset(b[r],0,sizeof b[r]);
            tot[r]=0;
            rep(i,n)if(i!=tr&&i!=ts)
            {
                for(int j=b[r^1][i]; j; j=ee[r^1][j].f)
                    if(ee[r^1][j].v!=tr&&ee[r^1][j].v!=ts)adds(r,i,ee[r^1][j].v,ee[r^1][j].c);
            }
            top=0;
            memset(tab,0,sizeof tab);
            for(int i=b[r^1][ts]; i; i=ee[r^1][i].f)if(ee[r^1][i].v!=tr)tab[ee[r^1][i].v]+=ee[r^1][i].c;
            for(int i=b[r^1][tr]; i; i=ee[r^1][i].f)if(ee[r^1][i].v!=ts)tab[ee[r^1][i].v]+=ee[r^1][i].c;
            rep(i,n)if(tab[i])add(r,ts,i,tab[i]);
        }
        printf("%d
",ans);
    }
}