Posted on 2010-08-20 18:20
acronix 阅读(225)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告 、
hzshuai解题中算法总结
题意:电脑装机,要买 N 个配件,现有两家公司A 、B分别有这些配件,但价格不同,现在要求买完配件所用最少的价钱,同时若两配件来自不同的公司,考虑兼容性,可能要花而外的钱买转换器。
分析:最小割转换到最大流,n个配件,n个顶点,源点连向各顶点的边表示A公司的配件,边权表示A公司的该配件的价钱;各顶点连向汇点的边表示B公司的配件,边权表示B公司的该配件的价格。当两配件来自不同公司有兼容性问题时,对应的顶点连双向边,边权为转换器的价格。构图完成,很显然,此图的最小割便是所求,因而可用求最大流即可。
收获:因为此题数据顶点和边的数量都很大,朴素的最大流勉强能应付,但用dinic求最大流,那速度可是相当的快,几倍的差别,甚至是TLE 和 AC的差别。所以好好用好魅力无穷的Dinic吧~~~
cpp代码:
#include <cstdio>
#include <algorithm>
using namespace std;
const int inf = 1<<28;
#define Max 510
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N,n,m; //sta is the sourse ,end is the end,N is the number of vector
int q[Max];
bool bfs(int s)
{
int front=0,rear=0;
for (int i = 0; i <= end; i++) //d[] is the deep
d[i] = -1;
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0; i<=N; i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end) return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i] -= a;
flow[i][k] += a;
sum -= a;
}
return os-sum;
}
int main()
{
int i,j,x,y,v;
while (scanf("%d %d",&n,&m) != EOF)
{
sta = 0; end = n+1;
for (i = 0; i <= end; i++)
for (j = 0; j <= end; j++)
flow[i][j] = 0;
for (i = 1; i <= n; i++)
scanf("%d",&flow[sta][i]);
for (i = 1; i <= n; i++)
scanf("%d",&flow[i][end]);
for (i = 1; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &v);
flow[x][y] = flow[y][x] += v;
}
int ret=0;
N = end;
while(bfs(sta))
ret += dinic(sta,inf);
printf("%d\n",ret);
}
return 0;
}