洛谷P2053 修车

修车修到jiry报废(滑稽)

题意：m个人修n个车，同时开始。

每辆车只能给一个人修。每个人修每辆车的用时都不同。

问怎样安排能使每辆车的等待时间总和最少。

解：

一直想的是用以流量表示一个人，没想到是一流量表示一辆车......

答案统计也想错了...应该是统计每辆车修的时候对它以及它后面车的贡献。

比如当前这辆车的后面还有k辆，那么时间就要乘k + 1

每辆车可以给每个人修，后面可以安排任意辆车。据此拆点，把每个人拆成n个。

源点向车连边，车向每个人的后面有几辆车(一共m * n个点)连边，然后连到汇点。

跑最小费用最大流即可。

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 #include <cstring>

 const int N = , M = , INF = 0x3f3f3f3f;

 struct Edge {

     int nex, v, c, len;

 }edge[M << ]; int top = ;

 int e[N], d[N], vis[N], pre[N], flow[N];

 std::queue<int> Q;

 int G[][];

 inline void add(int x, int y, int z, int w) {

     top++;

     edge[top].v = y;

     edge[top].c = z;

     edge[top].len = w;

     edge[top].nex = e[x];

     e[x] = top;

     top++;

     edge[top].v = x;

     edge[top].c = ;

     edge[top].len = -w;

     edge[top].nex = e[y];

     e[y] = top;

     return;

 }

 inline bool SPFA(int s, int t) {

     memset(d, 0x3f, sizeof(d));

     d[s] = ;

     flow[s] = INF;

     vis[s] = ;

     Q.push(s);

     while(!Q.empty()) {

         int x = Q.front();

         Q.pop();

         vis[x] = ;

         for(int i = e[x]; i; i = edge[i].nex) {

             int y = edge[i].v;

             if(edge[i].c && d[y] > d[x] + edge[i].len) {

                 d[y] = d[x] + edge[i].len;

                 pre[y] = i;

                 flow[y] = std::min(flow[x], edge[i].c);

                 if(!vis[y]) {

                     vis[y] = ;

                     Q.push(y);

                 }

             }

         }

     }

     return d[t] < INF;

 }

 inline void update(int s, int t) {

     int temp = flow[t];

     while(t != s) {

         int i = pre[t];

         edge[i].c -= temp;

         edge[i ^ ].c += temp;

         t = edge[i ^ ].v;

     }

     return;

 }

 inline int solve(int s, int t, int &cost) {

     int ans = ;

     cost = ;

     while(SPFA(s, t)) {

         ans += flow[t];

         cost += flow[t] * d[t];

         update(s, t);

     }

     return ans;

 }

 int m;

 inline int id(int x, int y) {

     return (x - ) * m + y;

 }

 int main() {

     int n;

     scanf("%d%d", &m, &n);

     for(int i = ; i <= n; i++) {

         for(int j = ; j <= m; j++) {

             scanf("%d", &G[i][j]);

         }

     }

     int s = (m + ) * n + ;

     int t = s + ;

     for(int a = ; a <= n; a++) {

         add(s, a, , );

         for(int j = ; j <= m; j++) {

             for(int i = ; i <= n; i++) {

                 add(a, n + id(i, j), , i * G[a][j]);

             }

         }

         for(int j = ; j <= m; j++) {

             add(n + id(a, j), t, , );

         }

     }

     int ans;

     solve(s, t, ans);

     printf("%.2f", 1.0 * ans / n);

     return ;

 }

AC代码

巴特西

洛谷P2053 修车

最新文章

热门文章