发布于 由itewqq

[二分图带权匹配][KM算法][图论][模型转化] SGU 206 Roads

https://cn.vjudge.net/problem/SGU-206

这个题乍一看不可做系列(难道不是吗)，像是跟生成树相关的问题。然而看了dalao的博客和论文之后总算搞明白了原来要转化为二分图模型。而之所以能转化就是因为里面的绝对值去掉不等式（去绝对值用的是贪心的思想，1-n-1之间的都要变小，n到m的都要变大）之后，非树边 j 和树边 i 的delta关系可以写成Di+Dj>=Ci-Cj,然后dalao们就想到了KM算法里的标杆与权值之间的不等式关系 鬼知道他们怎么想到的

KM算法的话，标杆是恒满足lx[i]+ly[j]>=w[i][j]的，而且跑完KM之后每一对都取到了等号，这时候可以证明Σlx[i]+Σly[i]取得最小值（参考王俊前辈集训队论文）而我们研究的问题是Di+Dj，那么其实可以把原图转换一个二分图出来，左边的节点代表树边（没错，一个点对应的是原图中的一条树边），右边的代表非树边，中间权值为Ci – Cj，其中C是原图中边的权值 。建好二分图之后跑一边KM即可。

所以现在关键的问题就在于怎么建二分图了。参考了dalao的做法，由于点和边的数量其实很少，所以直接非常暴力的dfs，从一条非树边的一个节点开始沿着树搜索，直到搜索到这条边的另一个节点才返回1，搜到其他的叶子都返回0（超级暴力有没有。。。）具体看代码。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
typedef long long LL;
const int maxn=400+5;//re! the 
const int maxm=405;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;


int nx,ny;
int g[maxn][maxn],w[maxn][maxn];
int link[maxn],lx[maxn],ly[maxn];
int slack[maxn];
bool  visx[maxn],visy[maxn];
bool dfs(int x)
{
    int tmp;
    visx[x]=true;
    for (int y=1;y<=ny;y++)
    {
        if(visy[y])continue;
        tmp=lx[x]+ly[y]-g[x][y];
        if(!tmp)
        {
            visy[y]=true;
            if(link[y]==-1||dfs(link[y]))
            {
                link[y]=x;
                return true;
            }
        }
        else if(slack[y]>tmp)
            slack[y]=tmp;
    }
    return false;
}

void KM()
{
    memset(link,-1,sizeof(link));
    memset(ly,0,sizeof(ly));
    for (int i=1;i<=nx;i++)
    {
        lx[i]=-INF;
        for (int j=1;j<=ny;j++)
            if(g[i][j]>lx[i])
            lx[i]=g[i][j];
    }

    for (int x=1;x<=nx;x++)
    {
        for (int i=1;i<=ny;i++)
            slack[i]=INF;
        while(true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x))break;
            int d=INF;
            for (int i=1;i<=ny;i++)
                if(!visy[i]&&d>slack[i])
                    d=slack[i];
            for (int i=1;i<=nx;i++)
                if(visx[i])
                    lx[i]-=d;
            for (int i=1;i<=ny;i++)//wtf? 2?
            {
                if(visy[i])ly[i]+=d;
                else slack[i]-=d;
            }
        }
    }
    return ;
}

int n,x[maxn],y[maxn],z[maxn];

int build_g(int pre,int u,int v, int id)//real nice ！可以说这个题全在这个操作了。。。。
{
    if(u==v)return 1;//只有找到了v才说明找到了那个环，其他的则是错误的路径
    for (int i=1;i<=n;i++)
    {
        if(pre!=i&&w[u][i]&&build_g(u,i,v,id))
        {
            g[w[u][i]][id]=z[w[u][i]]-z[id];
            return 1;//很重要，如果上面的返回1 那么说明已经找到了，直接返回
        }
    }
    return 0;//for the wrong path
}

int main()
{
    //freopen("roads.in","r",stdin);
    //freopen("roads.out","w",stdout);
    int m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)scanf("%d%d%d",&x[i],&y[i],&z[i]);
    for (int i=1;i

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。