修车 bzoj-1070 SCOI-2007
题目大意：有m个人要修n台车，每个工人修不同的车的时间不同，问将所有的车都修完，最少需要花费的时间。
注释：$2\le m\le 9$，$1\le n \le 60$
想法：想起了那句话...（如果题面复杂，dp状态不可描述，一看数据范围发现才几百，那八成是网络流了），一般这句话都是对的，除了那次在CF上遇到的爆搜.. ...
关于这道题，网上有题解在边上做技巧(完全没明白这样的意义)，我的做法时拆点。将每个点拆成n个，然后在这些被拆的点与车之间连边即可，保证每走一条边需要将之后的费用都统计进来。
具体地，将一个j工人拆成n个点，第k个点表示这个工人倒数第k个修车i，那么车i向工人j连一条容量为1，费用为k*w[i][j]，表示修自己的车的一个费用，和后面k-1个人等待的费用，就是算自己费用的同时算上别人的费用。注意这样倒着考虑，每个车连的边就只对关于同一个工人但是在他后面修车的有影响。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
#define N 610
#define M 76010
#define INF 0x3f3f3f
long long ans;
struct node{
int x,y,co,next,cap;
}edge[M];
int head[N],dis[N],pre[N];
bool vis[N];
int l,m,n,t,s,w;
void add(int x,int y,int c,int z)
{
l++;
edge[l].x=x;edge[l].y=y;edge[l].co=z;edge[l].cap=c;
edge[l].next=head[x];
head[x]=l;
}
bool spfa()
{
queue<int> q;
for(int i=0;i<=t;i++) {dis[i]=INF;vis[i]=0;}
memset(pre,0,sizeof(pre));
vis[s]=1;dis[s]=0;
q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();
vis[x]=0;
for (int i=head[x];i!=-1;i=edge[i].next)
{
int y=edge[i].y;
if (edge[i].cap && dis[x]+edge[i].co<dis[y])
{
pre[y]=i;
dis[y]=edge[i].co+dis[x];
if (!vis[y]) q.push(y), vis[y]=1;
}
}
}
if (dis[t]<INF) return 1; else return 0;
}
void minf()
{
int i=pre[t],cap=INF;
while(i)
{
cap=min(cap, edge[i].cap);
i=pre[edge[i].x];
}
i=pre[t];
while(i)
{
edge[i].cap-=cap;
edge[i^1].cap+=cap;
ans+=cap*edge[i].co;
i=pre[edge[i].x];
}
}
int main()
{
scanf("%d%d", &m, &n);
l=1;
memset(head,-1,sizeof head);
t=n+m*n+1;s=0;
for(int i=1;i<=n;i++)
{
add(s,i,1,0);
add(i,s,0,0);
for(int j=1;j<=m;j++)
{
scanf("%d", &w);
for(int k=1;k<=n;k++)
{
add(i, j*n+k, 1, k*w);
add(j*n+k, i, 0, -k*w);
}
}
}
for(int j=n+1;j<=m*n+n;j++)
{
add(j,t,1,0);
add(t,j,0,0);
}
ans=0;
while(spfa()) minf();
printf("%.2lf\n", (double)ans / n);
}
小结：记住一些题目的描述，有利于帮助我门迅速分析出切入点。