BZOJ3118 Orz the MST

Luogu

IDLGP10669

Time1000ms

Memory512MB

DifficultyP6

O2优化线性规划

给出一个带权的连通无向图，对于其中的每条边 $i$，在原来边权的基础上，其边权每增加 $1$ 需要付出的代价为 $a_i$，边权每减少 $1$ 需要付出的代价为 $b_i$。现在指定该图的一棵生成树，求通过修改边权，使得该生成树成为图的一棵最小生成树，需要付出的最少总代价。 ## Input 第一行两个正整数 $n,m$，表示图的点数和边数，结点以 $1\sim n$ 编号。接下来 $m$ 行，每行 $6$ 个正整数，$u_i,v_i,w_i,\textit{ff}_i,a_i,b_i$，表示一条边 $(u_i,v_i)$ 的权值为 $w_i$，在原边权基础上增加 $1$ 的代价为 $a_i$，减少 $1$ 的边权代价为 $b_i$，$\textit{ff}_i$ 若为 $1$ 则表示该边在指定的生成树中，若为 $0$ 则表示不在。数据保证 $\textit{ff}_i$ 值为 $1$ 的边刚好组成原图的一棵生成树。两点之间可能有多条不同的边，但没有连接同一点的边。 ## Output 输出一个正整数，表示所需付出的最少总代价。 [samples] ## Note **【样例解释】** 最优方案为： - $(1,4)$ 边权加 $2$，代价 $6$； - $(3,5)$ 边权加 $3$，代价 $3$； - $(3,6)$ 边权加 $4$，代价 $8$； - $(4,5)$ 边权减 $2$，代价 $4$；总代价为 $21$。 **【数据范围】** 对于 $100\%$ 的数据，$1\leq n\leq 300$，$1\leq m,w_i,a_i,b_i\leq 1000$。

Samples

Input #1

6 8
1 2 3 1 4 2
1 4 2 0 3 4
2 3 5 1 2 1
2 4 4 1 3 5
3 5 2 0 1 3
3 6 1 0 2 4
4 5 7 1 3 2
5 6 5 1 5 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "BZOJ3118 Orz the MST",
    "description": {
      "content": "给出一个带权的连通无向图，对于其中的每条边 $i$，在原来边权的基础上，其边权每增加 $1$ 需要付出的代价为 $a_i$，边权每减少 $1$ 需要付出的代价为 $b_i$。 现在指定该图的一棵生成树，求通过修改边权，使得该生成树成为图的一棵最小生成树，需要付出的最少总代价。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10669"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个带权的连通无向图，对于其中的每条边 $i$，在原来边权的基础上，其边权每增加 $1$ 需要付出的代价为 $a_i$，边权每减少 $1$ 需要付出的代价为 $b_i$。\n\n现在指定该图的一棵生成树，求通过修改边权，使得该生成树成为图的一棵最小生成树，需要付出的最少总代价。\n\n## Input\n\n第一行两个正整数 $n,m$，表示图的点数和边数，结点以 $1\\sim n$ 编号。\n\n接下来 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments