http://www.lydsy.com/JudgeOnline/problem.php?id=1070
题意:
思路:
神奇的构图。
因为排在后面的人需要等待前面的车修好,这里将每个技术人员拆成n个点,第k个点表示该技术人员倒数第k的顺序来修理该车,此时它的时间对于答案的贡献就是kw。
最后跑一遍最小费用流。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; int n,m; struct Edge
{
int from, to, cap, flow, cost;
Edge(int u, int v, int c, int f, int w) :from(u), to(v), cap(c), flow(f), cost(w) {}
}; struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];
int d[maxn];
int p[maxn];
int a[maxn]; void init(int n)
{
this->n = n;
for (int i = ; i<n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap, int cost)
{
edges.push_back(Edge(from, to, cap, , cost));
edges.push_back(Edge(to, from, , , -cost));
m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
} bool BellmanFord(int s, int t, int &flow, int & cost)
{
for (int i = ; i<n; i++) d[i] = INF;
memset(inq, , sizeof(inq));
d[s] = ; inq[s] = ; p[s] = ; a[s] = INF; queue<int> Q;
Q.push(s);
while (!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = ;
for (int i = ; i<G[u].size(); i++){
Edge& e = edges[G[u][i]];
if (e.cap>e.flow && d[e.to]>d[u] + e.cost){
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to]) { Q.push(e.to); inq[e.to] = ; }
}
}
} if (d[t] == INF) return false;
flow += a[t];
cost += d[t] * a[t];
for (int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[t];
edges[p[u] ^ ].flow -= a[t];
}
return true;
} int MincostMaxdflow(int s, int t){
int flow = , cost = ;
while (BellmanFord(s, t, flow, cost));
return cost;
}
}t; int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&m,&n))
{
int src=,dst=n*m+n+;
t.init(dst+);
for(int i=;i<=n;i++)
{
t.AddEdge(src,i,,);
for(int j=;j<=m;j++)
{
int x; scanf("%d",&x);
for(int k=;k<=n;k++)
t.AddEdge(i,j*n+k,,k*x);
}
}
for(int j=n+;j<=m*n+n;j++)
t.AddEdge(j,dst,,);
int ans = t.MincostMaxdflow(src,dst);
printf("%.2f\n",(double)ans/n);
}
return ;
}