KM算法( 二 )

G - Cyclic Tour
题意：
图中有n个点和m条有向边
现在要将该图分成若干环，每个环中至少有两个点。环与环不能有交点。问所有环的总长度最小为多少？
题解: ( 最小环长度 + km )
可以发现，每个点的入度和出度都是1。
如果每个点都拆成入点和出点，对于点u，可以拆成u和u’， u是入点，u’是出点。
若有边(u, v)，则u’ -> v连边
这样整个图转化为一个二分图。由于每个入点需要找一个出点连接，每个出点也要找一个入点连接，那么就是经典的二分图匹配问题。加上一个权值，就是二分图最优匹配问题。

    #include <cstring>
    #include <cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=105;
    const int INF=0x3f3f3f3f;
    int love[MAXN][MAXN];
    int eg[MAXN];
    int eb[MAXN];
    int vg[MAXN];
    int vb[MAXN];
    int sl[MAXN];
    int match[MAXN];
    int n,m;
    bool DFS(int girl)
    {
        vg[girl]=1;
        for(int boy=0;boy<m;boy++)
        {
            if(vb[boy]) continue;
            int gap=eg[girl]+eb[boy]-love[girl][boy];
            if(gap==0)
            {
                vb[boy]=1;
                if(match[boy]==-1||DFS(match[boy]))
                {
                    match[boy]=girl;
                    return true;
                }
            }
            else sl[boy]=min(sl[boy],gap);
        }
        return false;
    }
    int km()
    {
        memset(match,-1,sizeof(match));
        memset(eb,0,sizeof(eb));
        for(int i=0;i<n;i++)
        {
            eg[i]=love[i][0];
            for(int j=1;j<m;j++)
            {
                eg[i]=max(eg[i],love[i][j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            fill(sl,sl+m,INF);
            while(true)
            {
                memset(vg,0,sizeof(vg));
                memset(vb,0,sizeof(vb));
                if(DFS(i)) break;
                int d=INF;
                for(int j=0;j<m;j++)
                {
                    if(!vb[j])d=min(d,sl[j]);
                }
                if(d==INF) return 1;
                for(int j=0;j<n;j++)
                {
                    if(vg[j]) eg[j]-=d;
                }
                for(int j=0;j<m;j++)
                {
                    if(vb[j]) eb[j]+=d;
                    else sl[j]-=d;
                }
            }
        }
        int res=0,flag=0;
        for(int j=0;j<m;j++)
        {
            if(match[j]==-1||love[match[j]][j]==-INF) continue;
            res+=love[match[j]][j];
            flag++;
        }
        if(flag<n) res=1;
        return res;
    }
    int main()
    {
        int e;
        int u,v,val;
        while(scanf("%d%d",&n,&e)!=EOF)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    love[i][j]=-INF;
                }
            }
            for(int i=0;i<e;i++)
            {
                scanf("%d%d%d",&u,&v,&val);
                if(-val>love[u-1][v-1]) love[u-1][v-1]=-val;
            }
            m=n;
            printf("%d\n",-km());
        }
        return 0;
    }

H - Tour
题意:
同G题一样

    #include <cstring>
    #include <cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=210;
    const int INF=0x3f3f3f3f;
    int love[MAXN][MAXN];
    int eg[MAXN];
    int eb[MAXN];
    int vg[MAXN];
    int vb[MAXN];
    int sl[MAXN];
    int match[MAXN];
    int n,m;
    bool DFS(int girl)
    {
        vg[girl]=1;
        for(int boy=0;boy<m;boy++)
        {
            if(vb[boy]) continue;
            int gap=eg[girl]+eb[boy]-love[girl][boy];
            if(gap==0)
            {
                vb[boy]=1;
                if(match[boy]==-1||DFS(match[boy]))
                {
                    match[boy]=girl;
                    return true;
                }
            }
            else sl[boy]=min(sl[boy],gap);
        }
        return false;
    }
    int km()
    {
        memset(match,-1,sizeof(match));
        memset(eb,0,sizeof(eb));
        for(int i=0;i<n;i++)
        {
            eg[i]=love[i][0];
            for(int j=1;j<m;j++)
            {
                eg[i]=max(eg[i],love[i][j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            fill(sl,sl+m,INF);
            while(true)
            {
                memset(vg,0,sizeof(vg));
                memset(vb,0,sizeof(vb));
                if(DFS(i)) break;
                int d=INF;
                for(int j=0;j<m;j++)
                {
                    if(!vb[j])d=min(d,sl[j]);
                }
                if(d==INF) return 1;
                for(int j=0;j<n;j++)
                {
                    if(vg[j]) eg[j]-=d;
                }
                for(int j=0;j<m;j++)
                {
                    if(vb[j]) eb[j]+=d;
                    else sl[j]-=d;
                }
            }
        }
        int res=0,flag=0;
        for(int j=0;j<m;j++)
        {
            if(match[j]==-1||love[match[j]][j]==-INF) continue;
            res+=love[match[j]][j];
            flag++;
        }
        if(flag<n) res=1;
        return res;
    }
    int main()
    {
        int e;
        int u,v,val;
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&e);
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    love[i][j]=-INF;
                }
            }
            for(int i=0;i<e;i++)
            {
                scanf("%d%d%d",&u,&v,&val);
                if(-val>love[u-1][v-1]) love[u-1][v-1]=-val;
            }
            m=n;
            printf("%d\n",-km());
        }
        return 0;
    }

I - A new Graph Game
题意:
求哈密顿回路上的最小权
题解:( 最小环长度 + km )
因为是无向哈密顿图，所以每个点入度和出度必须为1，将每个点拆成u，u’，对于边<u,v>，连接边<u，v’>，<v，u’>;思路和G,H差不多

    #include <cstring>
    #include <cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=1010;
    const int INF=0x3f3f3f3f;
    int love[MAXN][MAXN];
    int eg[MAXN];
    int eb[MAXN];
    int vg[MAXN];
    int vb[MAXN];
    int sl[MAXN];
    int match[MAXN];
    int n,m;
    bool DFS(int girl)
    {
        vg[girl]=1;
        for(int boy=0;boy<m;boy++)
        {
            if(vb[boy]) continue;
            int gap=eg[girl]+eb[boy]-love[girl][boy];
            if(gap==0)
            {
                vb[boy]=1;
                if(match[boy]==-1||DFS(match[boy]))
                {
                    match[boy]=girl;
                    return true;
                }
            }
            else sl[boy]=min(sl[boy],gap);
        }
        return false;
    }
    int km()
    {
        memset(match,-1,sizeof(match));
        memset(eb,0,sizeof(eb));
        for(int i=0;i<n;i++)
        {
            eg[i]=love[i][0];
            for(int j=1;j<m;j++)
            {
                eg[i]=max(eg[i],love[i][j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            fill(sl,sl+m,INF);
            while(true)
            {
                memset(vg,0,sizeof(vg));
                memset(vb,0,sizeof(vb));
                if(DFS(i)) break;
                int d=INF;
                for(int j=0;j<m;j++)
                {
                    if(!vb[j])d=min(d,sl[j]);
                }
                if(d==INF) return 1;
                for(int j=0;j<n;j++)
                {
                    if(vg[j]) eg[j]-=d;
                }
                for(int j=0;j<m;j++)
                {
                    if(vb[j]) eb[j]+=d;
                    else sl[j]-=d;
                }
            }
        }
        int res=0,flag=0;
        for(int j=0;j<m;j++)
        {
            if(match[j]==-1||love[match[j]][j]==-INF) continue;
            res+=love[match[j]][j];
            flag++;
        }
        if(flag<n) res=1;
        return res;
    }
    int main()
    {
        int e;
        int u,v,val;
        int t;
        scanf("%d",&t);
        for(int cas=1;cas<=t;cas++)
        {
            scanf("%d%d",&n,&e);
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    love[i][j]=-INF;
                }
            }
            for(int i=0;i<e;i++)
            {
                scanf("%d%d%d",&u,&v,&val);
                if(-val>love[u-1][v-1])
                {
                        love[u-1][v-1]=-val;
                        love[v-1][u-1]=-val;
                }
            }
            m=n;
            int res=-km();
            if(res!=-1)
            printf("Case %d: %d\n",cas,res);
            else printf("Case %d: NO\n",cas);

        }
        return 0;
    }

J - Card Game
题意:
就是给n个字符串，然后对于任意两个字符串进行匹配，第一个倒序，第二个正序，找它们的最长公共前缀长度，就是它们的分数，自己和自己匹配分数为0，然后把这些字符串组成一些圈，求能得到的最大分数
题解: ( 最小环长度 + km )
因为是求出环,所以可以用匹配做;每个点都与另外所有的点相连,然后预处理求出连接两点得到的分数;

    #include <cstring>
    #include <cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=205;
    const int INF=0x3f3f3f3f;
    int love[MAXN][MAXN];
    int eg[MAXN];
    int eb[MAXN];
    int vg[MAXN];
    int vb[MAXN];
    int sl[MAXN];
    int match[MAXN];
    int n,m;
    bool DFS(int girl)
    {
        vg[girl]=1;
        for(int boy=0;boy<m;boy++)
        {
            if(vb[boy]) continue;
            int gap=eg[girl]+eb[boy]-love[girl][boy];
            if(gap==0)
            {
                vb[boy]=1;
                if(match[boy]==-1||DFS(match[boy]))
                {
                    match[boy]=girl;
                    return true;
                }
            }
            else sl[boy]=min(sl[boy],gap);
        }
        return false;
    }
    int km()
    {
        memset(match,-1,sizeof(match));
        memset(eb,0,sizeof(eb));
        for(int i=0;i<n;i++)
        {
            eg[i]=love[i][0];
            for(int j=1;j<m;j++)
            {
                eg[i]=max(eg[i],love[i][j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            fill(sl,sl+m,INF);
            while(true)
            {
                memset(vg,0,sizeof(vg));
                memset(vb,0,sizeof(vb));
                if(DFS(i)) break;
                int d=INF;
                for(int j=0;j<m;j++)
                {
                    if(!vb[j])d=min(d,sl[j]);
                }
                for(int j=0;j<n;j++)
                {
                    if(vg[j]) eg[j]-=d;
                }
                for(int j=0;j<m;j++)
                {
                    if(vb[j]) eb[j]+=d;
                    else sl[j]-=d;
                }
            }
        }
        int res=0;
        for(int j=0;j<m;j++)
        {
            res+=love[match[j]][j];
        }
        return res;
    }

int judge(char s1[], char s2[])
{
    int res = 0;
    for(int i = strlen(s1) - 1, j = 0;i>=0&&j<strlen(s2); i--, j++)
        if(s1[i] != s2[j]) return res;
        else res++;
    return res;
}
    int main()
    {
        char str[MAXN][1010];
        while(~ scanf("%d", &n))
        {
            m=n;
            for(int i = 0; i < n; i++)
                scanf(" %s", str[i]);
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    if(i == j) love[i][j] = 0;
                    else love[i][j] = judge(str[i], str[j]);
            printf("%d\n", km());
        }
        return 0;
    }

K - Similarity
题意:
n，k，m表示序列长度为n，保证序列中最多有k种字母，有一种答案和m份试卷（每份试卷的字母可以随意转换，但是一种字母只能换成一种字母,同种字母），问其正确率最大可能为多少
题解:
求出每个字母转换为其他字母后的答案的最大的正确数,即试卷的字母转换为答案的字母的哪种方案使得正确总数最高;每个试卷字母u,转换为每个答案字母v后的正确数为val,则在u,v间连接一条边,graph[u][v]=val;最后就是求出二分图的最大权;
这里参考别人的代码才知道求出val的比较精妙的办法是Θ(n)的复杂度
　　假设u转换为v,那么在某个位置pos,可以存在paper[pos]=u,answer[pos]=v,那么这个位置就是有效的位置,所以graph[u][v]++;
( graph[u][v]表示paper中的所有u转换为v后,可以和answer正确对上的答案总数比如paper为ABA,answer为CDC,假设A转换为C,那么graph[A][C]=2;假设A转换为D,那么grpah[A][D]=0 )

    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int MAXN=35;
    const int INF=0x3f3f3f3f;
    int love[MAXN][MAXN];
    int eg[MAXN];
    int eb[MAXN];
    int vg[MAXN];
    int vb[MAXN];
    int sl[MAXN];
    int match[MAXN];
    int n,m;
    bool DFS(int girl)
    {
        vg[girl]=1;
        for(int boy=0;boy<m;boy++)
        {
            if(vb[boy]) continue;
            int gap=eg[girl]+eb[boy]-love[girl][boy];
            if(gap==0)
            {
                vb[boy]=1;
                if(match[boy]==-1||DFS(match[boy]))
                {
                    match[boy]=girl;
                    return true;
                }
            }
            else sl[boy]=min(sl[boy],gap);
        }
        return false;
    }
    int km()
    {
        memset(match,-1,sizeof(match));
        memset(eb,0,sizeof(eb));
        for(int i=0;i<n;i++)
        {
            eg[i]=love[i][0];
            for(int j=1;j<m;j++)
            {
                eg[i]=max(eg[i],love[i][j]);
            }
        }
        for(int i=0;i<n;i++)
        {
            fill(sl,sl+m,INF);
            while(true)
            {
                memset(vg,0,sizeof(vg));
                memset(vb,0,sizeof(vb));
                if(DFS(i)) break;
                int d=INF;
                for(int j=0;j<m;j++)
                {
                    if(!vb[j])d=min(d,sl[j]);
                }
                for(int j=0;j<n;j++)
                {
                    if(vg[j]) eg[j]-=d;
                }
                for(int j=0;j<m;j++)
                {
                    if(vb[j]) eb[j]+=d;
                    else sl[j]-=d;
                }
            }
        }
        int res=0;
        for(int j=0;j<m;j++)
        {
            if(match[j]==-1) continue;
            res+=love[match[j]][j];
        }
        return res;
    }
    int main()
    {
        char answer[10010];
        char paper[10010];
        int t,len,k,e;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d",&len,&k,&e);
            for(int i=0;i<len;i++)
            {
                scanf(" %c",&answer[i]);
            }
            while(e--)
            {
                for(int i=0;i<len;i++)
                {
                    scanf(" %c",&paper[i]);
                }
                memset(love,0,sizeof(love));
                n=m=30;
                for(int i=0;i<len;i++)
                {
                    int u=paper[i]-'A';
                    int v=answer[i]-'A';
                    love[u][v]++;
                }
                printf("%.4f\n",km()*1.0/len);
            }
        }
        return 0;
    }

L - Mining Station on the Sea
题意:
海上有m个油田,n个港口和n条船,m>n,油田与油田之间有航道以及距离,港口与油田之间也有航道和距离。一开始n条船各自停在的油田中,现在船要开会港口,每个港口只能停一条船,求出开回港口的最短路径。
题解: ( 最短路 + km )
船可以直接从原来位置开回港口,也可以先开到别的油田再开回港口,所以我们先求出每条船开回各个港口的最短路径,也就是对每条船都进行一次单源最短路径,得出船到港口的最短距离,然后再对每条船和每个港口建立二分图,值是船i到港口j的最短路径,然后就是二分图最小权匹配了。注意:因为油田是中转站,港口是终点站,所以油田之间的连边是双边的,而港口和油田的来连边是单向的(为了防止船从港口跑回油田)

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=330;
const int MAXE=1000010;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;edge[cnt].val=val;
    edge[cnt].next=head[u];head[u]=cnt++;
}
int dis[MAXN],inqueue[MAXN];
void spfa_bfs(int st)
{
    memset(dis,INF,sizeof(dis));
    memset(inqueue,0,sizeof(inqueue));
    dis[st]=0;
    int u,v,i;
    queue<int> que;
    que.push(st);
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        inqueue[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
                if(!inqueue[v])
                {
                    inqueue[v]=1;
                    que.push(v);
                }
            }
        }
    }
}
const int MAX=110;
int love[MAX][MAX],slack[MAX];
int visb[MAX],visg[MAX];
int eb[MAX],eg[MAX];
int n,m,match[MAX];
bool DFS(int girl)
{
    visg[girl]=true;
    for(int boy=1;boy<=n;boy++)
    {
        if(visb[boy]) continue;
        int gap=eb[boy]+eg[girl]-love[girl][boy];
        if(gap==0)
        {
            visb[boy]=1;
            if(match[boy]==-1||DFS(match[boy]))
            {
                match[boy]=girl;
                return true;
            }
        }
        else slack[boy]=min(slack[boy],gap);
    }
    return false;
}
int km()
{
    memset(eb,0,sizeof(eb));
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        eg[i]=love[i][1];
        for(int j=2;j<=n;j++)
        {
            eg[i]=max(eg[i],love[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        memset(slack,INF,sizeof(slack));
        while(true)
        {
            memset(visb,0,sizeof(visb));
            memset(visg,0,sizeof(visg));
            if(DFS(i)) break;
            int d=INF;
            for(int i=1;i<=n;i++)
            {
                if(!visb[i]) d=min(d,slack[i]);
            }
            for(int i=1;i<=n;i++)
            {
                if(visg[i]) eg[i]-=d;
                if(visb[i]) eb[i]+=d;
                else     slack[i]-=d;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res+=love[match[i]][i];
    }
    return res;
}
int main()
{
    int k,p,st[MAXN],u,v,val;
    while(scanf("%d%d%d%d",&n,&m,&k,&p)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&st[i]);
        }
        memset(head,-1,sizeof(head));
        cnt=0;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        for(int i=0;i<p;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(v,u+200,val);
        }
        for(int i=1;i<=n;i++)
        {
            spfa_bfs(st[i]);
            for(int j=1;j<=n;j++)
            {
                love[i][j]=-dis[j+200];
            }
        }
        printf("%d\n",-km());
    }
}

M - Assignment
题意:
给出一个二分图以及相应的权重,再给出一个原来的匹配,要求在修改原来的匹配最少的情况下求出最大权匹配。问修改的匹配数目是多少以及比原来的匹配增加了多少?
题解: ( km : 优先匹配原先的边 )
　　首先,如果某条边的最优匹配和原来的匹配一致,那么我们要优先选择原来的那个匹配边。
怎么做呢?

唯一的办法就是增加原来的匹配边的权重,这样就可以优先匹配到原来的边了。

但是，这样做会不会使得匹配的最大权的值不正确？（可能偏大）

假设最多有n个点,先把原来的所有边都乘以k倍(k>n)，再对原来的匹配边增加1,那么求出最大权后,得出的结果要除以k,因为n<k,而原来的匹配边加1的得出的最大权-正确的最大权,就是原来的匹配边加1所带来的影响(这个影响最多增加n：当最大权匹配和原来匹配一致时),但是这个影响除以k就是0了,所以求出的最大权还是正确的；同时，因为原配边加１，所以它会优先选择原匹配边了！　ｗｏｃ！ｗｏｃ！

再来分析这样一个问题：它与原来的匹配边相比，修改了多少条匹配？

假设ans是最大权匹配结果(未除以k),因为原匹配边加1,其他边不变,所以ans%k就是原匹配边的个数,那么改变的匹配数就是n-ans%k(从反面讲,如果没有一条边加1,那么ans%k==0)

啊,蒟蒻只能学习别人的思路~~~

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=60;
const int INF=0x7fffffff;
int eb[MAXN],eg[MAXN];
int match[MAXN];
int vb[MAXN],vg[MAXN];
int slack[MAXN];
int love[MAXN][MAXN];
int n,m,oldSum;
bool DFS(int girl)
{
    vg[girl]=true;
    for(int boy=1;boy<=m;boy++)
    {
        if(vb[boy]) continue;
        int gap=eg[girl]+eb[boy]-love[girl][boy];
        if(gap==0)
        {
            vb[boy]=1;
            if(match[boy]==-1||DFS(match[boy]))
            {
                match[boy]=girl;
                return true;
            }
        }
        else slack[boy]=min(slack[boy],gap);
    }
    return false;
}
void KM()
{
    memset(match,-1,sizeof(match));
    memset(eb,0,sizeof(eb));
    for(int i=1;i<=n;i++)
    {
        eg[i]=love[i][1];
        for(int j=2;j<=m;j++)
        {
            eg[i]=max(eg[i],love[i][j]);
        }
    }

    for(int i=1;i<=n;i++)
    {
        fill(slack+1,slack+1+m,INF);
        while(true)
        {
            memset(vg,0,sizeof(vg));
            memset(vb,0,sizeof(vb));
            if(DFS(i)) break;

            int d=INF;
            for(int j=1;j<=m;j++)
            {
                if(!vb[j]) d=min(d,slack[j]);
            }
            for(int j=1;j<=n;j++)
            {
                if(vg[j]) eg[j]-=d;
            }
            for(int j=1;j<=m;j++)
            {
                if(vb[j]) eb[j]+=d;
                else slack[j]-=d;
            }

        }
    }
    int res=0;
    for(int i=1;i<=m;i++)
    {
        if(match[i]==-1) continue;
        res+=love[match[i]][i];
    }
    printf("%d %d\n",n-res%100,res/100-oldSum/100);
}
int main()
{
    int tmp;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&love[i][j]);
                love[i][j]*=100;
            }
        }
        oldSum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&tmp);
            love[i][tmp]+=1;
            oldSum+=love[i][tmp];
        }
        KM();
    }
}

N - My Brute
题意:
有两队人,x队和y队,每队都是n人,x队每个人的攻击力为ai,血量为pi;y队每个人攻击力bi,血量为hi。有一个计分数组v[n],假设x队的第i个人和y队某个队员打架输了,x队扣分v[i];赢了,x队积分v[i];打架的方式是x队队员先出手,y队队员扣血a,然后再到y出手,直到某个人血量<=0才结束,血量大于0的人赢。假设一开始的打架顺序是x队和y队一一对应,即第一个对第一个....求出x队的最大积分,并且求出和原匹配的匹配相似率。
题解:( km : 优先匹配原先的边 )
建边的时候模拟下打架就可以了,每个x队队员都与y队队员打架,建边;
至于匹配相似率,其实M题一样的做法。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=110;
const int INF=0x7fffffff;
int v[MAXN],h[MAXN],p[MAXN],a[MAXN],b[MAXN];
int eb[MAXN],eg[MAXN];
int match[MAXN];
int vb[MAXN],vg[MAXN];
int slack[MAXN];
int love[MAXN][MAXN];
int n,m;
bool DFS(int girl)
{
    vg[girl]=true;
    for(int boy=1;boy<=m;boy++)
    {
        if(vb[boy]) continue;
        int gap=eg[girl]+eb[boy]-love[girl][boy];
        if(gap==0)
        {
            vb[boy]=1;
            if(match[boy]==-1||DFS(match[boy]))
            {
                match[boy]=girl;
                return true;
            }
        }
        else slack[boy]=min(slack[boy],gap);
    }
    return false;
}
void KM()
{
    memset(match,-1,sizeof(match));
    memset(eb,0,sizeof(eb));
    for(int i=1;i<=n;i++)
    {
        eg[i]=0;
        for(int j=1;j<=m;j++)
        {
            eg[i]=max(eg[i],love[i][j]);
        }
    }

    for(int i=1;i<=n;i++)
    {
        fill(slack+1,slack+1+m,INF);
        while(true)
        {
            memset(vg,0,sizeof(vg));
            memset(vb,0,sizeof(vb));
            if(DFS(i)) break;

            int d=INF;
            for(int j=1;j<=m;j++)
            {
                if(!vb[j]) d=min(d,slack[j]);
            }
            for(int j=1;j<=n;j++)
            {
                if(vg[j]) eg[j]-=d;
            }
            for(int j=1;j<=m;j++)
            {
                if(vb[j]) eb[j]+=d;
                else slack[j]-=d;
            }

        }
    }
    int res=0;
    for(int i=1;i<=m;i++)
    {
        res+=love[match[i]][i];
    }
    if(res<=0) printf("Oh, I lose my dear seaco!\n");
    else printf("%d %.3lf%%\n",res/100,100.0*(res%100)/n);
}
int fight(int i,int j)
{
    int hpi=h[i],hpj=p[j];//两者血量
    int vi=a[i],vj=b[j];//两者攻击
    while(hpi && hpj)
    {
        hpj-=vi;
        if(hpj<=0) return v[i];
        hpi-=vj;
        if(hpi<=0) return -v[i];
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF,n)
    {
        m=n;
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        for(int i=1;i<=n;i++) scanf("%d",&h[i]);
        for(int i=1;i<=n;i++) scanf("%d",&p[i]);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                love[i][j]=fight(i,j);
                love[i][j]*=100;
                if(i==j) love[i][j]+=1;
            }
        }
        KM();
    }
}

R - Minimum Cost
题意:
有n个商店,m个仓库,k种商品。给出每个商店需要的每种商品的数目,每个仓库含有的每种商品的数目,以及每个商品 i从仓库 k 运到商店 j 需要的费用,求出供货费用最少的匹配
题解:( km + 拆点 )
先来看只有一种商品的情况,已知每个商店需要这种商品的数目以及每个仓库的库存,假设从某个仓库运到某个商店,那么两者连边,问题是:有些商店不需要这种商品,有些仓库没有这种商品,而且一个仓库的货物不一定分给一个商店,这样子就不符合二分图了!
所以,我们可以对仓库和商店进行拆点:假设仓库i有n1个商品,那就把仓库分成n1个点;假设商店j需要n2个商品,那就把商店分成n2个点,然后n1的每个点与n2的每个点连边,边权为费用。这样子建图就是二分图了!仓库的每个拆分点都和商店的每个拆分点连边,然后求最小权匹配。
然后,对k种商品都这样做,即可得k个商品的最小供货费用。
ps:其实这道题可以拆点是因为题目说每种商品供,需都不大于3,所以才可以拆点,如果商品数目很大时,还是要用最大流来做。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=200;
const int INF=0x3f3f3f3f;
int love[MAXN][MAXN],slack[MAXN];
int visb[MAXN],visg[MAXN];
int eb[MAXN],eg[MAXN];
int match[MAXN],n,m;
bool DFS(int girl)
{
    visg[girl]=true;
    for(int boy=1;boy<=m;boy++)
    {
        if(visb[boy]) continue;
        int gap=eb[boy]+eg[girl]-love[girl][boy];
        if(gap==0)
        {
            visb[boy]=1;
            if(match[boy]==-1||DFS(match[boy]))
            {
                match[boy]=girl;
                return true;
            }
        }
        else slack[boy]=min(slack[boy],gap);
    }
    return false;
}
int km()
{
    memset(eb,0,sizeof(eb));
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        eg[i]=love[i][1];
        for(int j=2;j<=m;j++)
        {
            eg[i]=max(love[i][j],eg[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        memset(slack,INF,sizeof(slack));
        while(true)
        {
            memset(visb,0,sizeof(visb));
            memset(visg,0,sizeof(visg));
            if(DFS(i)) break;
            int d=INF;
            for(int i=1;i<=m;i++)
            {
                if(!visb[i]) d=min(d,slack[i]);
            }
            for(int i=1;i<=n;i++)
            {
                if(visg[i]) eg[i]-=d;
            }
            for(int i=1;i<=m;i++)
            {
                if(visb[i]) eb[i]+=d;
                else slack[i]-=d;
            }
        }
    }
    int res=0;
    for(int i=1;i<=m;i++)
    {
        if(match[i]==-1) continue;
        res+=love[match[i]][i];
    }
    return res;
}
int kind[51][51][51];// i, j, k:一个 商品 i 从 仓库 k 运到 商店 j  需要的费用
int shop[51][51];//商店 i,需要 货物 j 的件数
int store[51][51];//仓库 i 有 货物 j 件数
int cpy[MAXN],cpx[MAXN];
int main()
{
    int N,M,K;//商店 仓库 商品种类
    while(scanf("%d%d%d",&N,&M,&K)!=EOF,N+M+K)
    {
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=K;j++)
            {
                scanf("%d",&shop[i][j]);
            }
        }
        for(int i=1;i<=M;i++)
        {
            for(int j=1;j<=K;j++)
            {
                scanf("%d",&store[i][j]);
            }
        }
        for(int i=1;i<=K;i++)
        {
            for(int j=1;j<=N;j++)
            {
                for(int k=1;k<=M;k++)
                {
                    scanf("%d",&kind[i][j][k]);
                }
            }
        }
        bool flag=false;
        for(int i=1;i<=K;i++)
        {
            int need=0,have=0;
            for(int j=1;j<=N;j++) need+=shop[j][i];
            for(int j=1;j<=M;j++) have+=store[j][i];
            if(have<need)
            {
                flag=true;
                break;
            }
        }
        if(flag)
        {
            printf("-1\n");
            continue;
        }
        int res=0;
        for(int i=1;i<=K;i++)
        {
            int currx=0,curry=0;
            for(int j=1;j<=N;j++)
            {
                for(int k=1;k<=shop[j][i];k++)
                {
                    cpx[++currx]=j;
                }
            }
            for(int j=1;j<=M;j++)
            {
                for(int k=1;k<=store[j][i];k++)
                {
                    cpy[++curry]=j;
                }
            }
            for(int j=1;j<=currx;j++)
            {
                for(int k=1;k<=curry;k++)
                {
                    love[j][k]=-kind[i][cpx[j]][cpy[k]];
                }
            }
            n=currx;m=curry;
            res+=-km();
        }
        printf("%d\n",res);
    }
}

T - The Windy's
题意:
有N个工件要在M个机器上加工,有一个N*M的矩阵描述其加工时间。
同一时间内每个机器只能加工一个工件,问加工完所有工件后，使得平均加工时间最小（等待的时间+加工的时间）。
题解: (拆点 + km )
假设某个机器处理了k个玩具，时间分别为a1,a2…..,ak
那么该机器耗费的时间为a1+（a1+a2）+（a1+a2+a3）.......（a1+a2+...ak）
即a1*k + a2 * (k - 1) + a3 * (k - 2).... + ak
ai玩具在某个机器上倒数第k个处理，所耗费全局的时间为ai*k
对每个机器，最多可以处理n个玩具，拆成n个点，1~n分别代表某个玩具在这个机器上倒数第几个被加工的,对于每个玩具i，机器j中拆的每个点k，连接一条w[i][j]*k权值的边
神一般的题,蒟蒻只能看别人的思路!

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 3000;
const int INF = 0x3f3f3f3f;

int love[60][MAXN];   
int ex_girl[MAXN];      
int ex_boy[MAXN];       
bool vis_girl[MAXN];    
bool vis_boy[MAXN];    
int match[MAXN];      
int slack[MAXN];       

int n,m;
bool dfs(int girl)
{
    vis_girl[girl] = true;

    for (int boy = 0; boy < m; ++boy) {

        if (vis_boy[boy]) continue;

        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

        if (gap == 0) {  
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {   
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  
        }
    }

    return false;
}

int km()
{
    memset(match, -1, sizeof match);   
    memset(ex_boy, 0, sizeof ex_boy);   

    for (int i = 0; i < n; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < m; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }
    for (int i = 0; i < n; ++i) {

        fill(slack, slack + m, INF);

        while (1) {
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);

            if (dfs(i)) break;

            int d = INF;
            for (int j = 0; j < m; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);
            if(d==INF) return -1;
            for (int j = 0; j < n; ++j) {
                if (vis_girl[j]) ex_girl[j] -= d;
            }

            for (int j = 0; j < m; ++j) {
                if (vis_boy[j]) ex_boy[j] += d;
                else slack[j] -= d;
            }
        }
    }

    int res = 0;
    for(int i = 0; i < m; i++){
        if(match[i]==-1)
            continue;
        res += love[match[i]][i];
    }
    return res;
}
int main()
{
    int t,x,y,cost,cnt;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&y);
        for(int i=0;i<x;i++)
        {
            cnt=0;
            for(int j=0;j<y;j++)
            {
                scanf("%d",&cost);
                for(int k=1;k<=x;k++)
                {
                    love[i][cnt++]=-k*cost;
                }
            }
        }
        n=x;m=x*y;
        int sum=km();
        printf("%.6f\n",-sum*1.0/n);
    }
}

最后编辑于：2017.12.10 01:54:08

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,132评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,802评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,566评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,858评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,867评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,695评论 1赞 282
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,064评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,705评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,915评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,677评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,796评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,432评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,041评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,992评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,223评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,185评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,535评论 2赞 343

KM算法( 二 )

推荐阅读更多精彩内容