[SPOJ412 COVER]特殊图的最小费用流巧妙优化

【题目地址】https://www.spoj.pl/problems/COVER/
【题目大意】
有n个点，m条有向边，这m条有向边的权值w=cost[x]+cost[y]，求k条边满足：
1、这k条边之间没有共起点和共终点的
2、这k条边的权和最小
【算法分析】
容易建图：
将n个点每个点拆成(i,i’)
然后对于有向边(x,y)，连边(x,y’)，该边权为cost[x]+cost[y]
于是相当于对这个二分图，求k次最小费用流的增广。
然后由于m太大，我们需要更快的算法。
对于观察每次增广，实际上就是匈牙利算法中的找交错轨，
并且新增的权总为增广路中的cost[起点]+cost[终点]
然后我们可以利用这个性质，将cost排序，然后有：当终点一样的情况下，让前面的先匹配比较好。
所以一个点只用进去一次就可以了。
最后就是每次枚举从某一点出发找增广路，找出本次增广增加的费用最小的。
然后去实现这个增广即可。
。。。罗嗦了这么多，结合程序看吧= =
【其它】
时间复杂度O(k*(n+m))
【CODE】
#include #include #include const int N=10005;
const int INF=1000000000;
struct gtp{int y,next;}g[1001111];
int n,m,k,ans,times;
int ls[N],link[N],v[N],cost[N][2],zz[N],To_y[N],cx[N];

void Read(int &x){
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
for (x=0;ch>=’0′ && ch<='9';ch=getchar())
x=x*10+ch-‘0’;
}

int cmp(const void *x,const void *y){return ((int*)x)[0]-((int*)y)[0];}

void init(){
memset(ls,0,sizeof(ls));
memset(link,0,sizeof(link));
memset(cx,0,sizeof(cx));
Read(k); Read(n); Read(m);
for (int i=1;i<=n;i++){
Read(cost[i][0]);
cost[i][1]=i;
}
qsort(&cost[1][0],n,sizeof(int)*2,cmp);
for (int i=1;i<=n;i++) zz[cost[i][1]]=i;
for (int i=1,x,y;i<=m;i++){
Read(x); Read(y);
x=zz[x]; y=zz[y];
g[i].y=y; g[i].next=ls[x]; ls[x]=i;
}
}

int Try(int p){
int res=INF,tmp;
for (int t=ls[p];t;t=g[t].next)
if (!v[g[t].y]){
v[g[t].y]=1;
if (!link[g[t].y]) tmp=cost[g[t].y][0];
else tmp=Try(link[g[t].y]);
if (tmp res=tmp;
To_y[p]=g[t].y;
}
}
return res;
}

void expand(int p){
int q=link[To_y[p]];
link[To_y[p]]=p;
if (q) expand(q);
}

void solve(){
ans=0;
for (int i=1;i<=k;i++){
memset(v+1,0,sizeof(int)*n);
memset(To_y+1,0,sizeof(int)*n);
int now=INF,nowi,tmp;
for (times=1;times<=n;times++)
if (cx[times]==0){
tmp=cost[times][0]+Try(times);
if (tmp now=tmp;
nowi=times;
}
}
if (now==INF){
printf("NONEn");
return;
}
ans+=now;
expand(nowi);
cx[nowi]=1;
}
printf("%dn",ans);
}

int main(){
int Tc;
Read(Tc);
for (int i=1;i<=Tc;i++){
init();
solve();
}
}