POJ3686 The Windy's

标签：bool   inf   getchar   ==   ios   read   return   putc   sizeof   

嘟嘟嘟

刚做费用流，思路完全不对呀……
应该这么想（应该说敢这么想）：这道题的关键在于怎么体现这个玩具是第几个加工的，只有这才能求出他的加工时间（因为加工时间包括等待时间）。
但等待时间不好求，因此要换个思路想：加工这个玩具会对别的玩具的加工时间造成多少影响。
假设三个玩具\(i, j, k\)依次在同一个工厂中被加工出来，那么总时间\(T = t_i + (t_i + t_j) + (t_i + t_j + t_k) = 3 * t_i + 2 * t_j + t_k\)。所以一个玩具对总时间的贡献是：加工次序\(*\)制作时间。
那么建图就有思路了：把每一个工厂拆成\(n\)个点，代表加工次序。对于每一个玩具\(i\)，向每一个工厂\(j\)的每一个加工次序的点\(k\)连一条容量为1，费用为\(k * cost_{i, j}\)的边。然后从源点向玩具连边，从每一个拆开的的工厂向汇点连边。
跑费用流。
最后要提醒的是算好空间。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define enter puts("") 
#define space putchar(‘ ‘)
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int N = 50;
const int maxn = N + N * N + 5;
const int maxe = N + N * N + N * N * N + 5;
inline ll read()
{
  ll ans = 0;
  char ch = getchar(), last = ‘ ‘;
  while(!isdigit(ch)) last = ch, ch = getchar();
  while(isdigit(ch)) ans = (ans = 10) write(x / 10);
  putchar(x % 10 + ‘0‘);
}

int n, m, s, t, a[N + 5][N + 5];
struct Edge
{
  int nxt, from, to, cap, c;
}e[maxe  q; q.push(s);
  while(!q.empty())
    {
      int now = q.front(); q.pop(); in[now] = 0;
      for(int i = head[now], v; i != -1; i = e[i].nxt)
    {
      v = e[i].to;
      if(e[i].cap > 0 && dis[now] + e[i].c 

POJ3686 The Windy's

标签：bool   inf   getchar   ==   ios   read   return   putc   sizeof   

原文地址：https://www.cnblogs.com/mrclr/p/10011230.html