KM算法( 二 )
2017-08-16 本文已影响0人
Gitfan
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);
}
}
