{"problem":{"name":"[湖北省选模拟 2023] 棋圣 / alphago","description":{"content":"小 K 是一名棋手，厌倦了传统围棋之后，他发明了一种新式围棋。 新式围棋是一种单人游戏。这个游戏的棋盘是一张包含 $n$ 个顶点，$m$ 条边的无向连通图，并且不存在重边和自环。同时，每条边有一个权值，第 $i$ 条边的权值为 $w_i$。 游戏开始时，每个顶点上可能有一颗黑棋或者一颗白棋，或者什么也没有。**至少有一个顶点上没有棋子。** 接下来，玩家需要进行若干次操作。每次的操作形式如下：","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9542"},"statements":[{"statement_type":"Markdown","content":"小 K 是一名棋手，厌倦了传统围棋之后，他发明了一种新式围棋。\n\n新式围棋是一种单人游戏。这个游戏的棋盘是一张包含 $n$ 个顶点，$m$ 条边的无向连通图，并且不存在重边和自环。同时，每条边有一个权值，第 $i$ 条边的权值为 $w_i$。\n\n游戏开始时，每个顶点上可能有一颗黑棋或者一颗白棋，或者什么也没有。**至少有一个顶点上没有棋子。** 接下来，玩家需要进行若干次操作。每次的操作形式如下：\n\n首先，选定一个上面没有棋子的顶点 $u$。可以说明，在题目数据范围下，一定存在这样的顶点。\n\n接下来，对于每一颗棋子，若它位于顶点 $v$，则玩家需任选一条从 $v$ 到 $u$ 的**简单路径**，并将这颗棋子沿着这条简单路径移动一步。形式化地，一条简单路径为一个顶点序列 $\\{p_1,p_2 \\ldots p_k\\}$，满足 $p_1 = v$，$p_k = u$ ，$p_1,p_2 \\ldots p_k$ **互不相同**，且 $p_i$ 和 $p_{i+1}$ 之间存在一条边。在操作之后，这颗棋子将被移动至顶点 $p_2$。\n\n需要注意的是，虽然在游戏开始时每个顶点上至多存在一颗棋子，但在若干次操作之后一个顶点上可能有多个棋子。对于同一个顶点上的不同棋子，一次操作中选取的简单路径可以不同。\n\n玩家可以在进行任意次操作（可以是 $0$ 次）之后进行**点目**，即结算游戏分数。对于每一对颜色不同的棋子，若它们所在的顶点之间由一条权值为 $w$ 的边直接相连，则称它们**围住了这条边**，会使玩家得到 $w$ 的**目数**。而一个玩家所得到的**目数**即所有棋子对产生的**目数**之和。\n\n现小 K 给了你一张游戏开始时的棋盘，请你帮他求出在这张棋盘上最多可能得到的**目数**。\n\n## Input\n\n输入共 $m+k+1$ 行。\n\n第一行三个整数 $n,m,k$，分别表示点和边的数量，以及棋子的数量。\n\n接下来 $k$ 行，每行两个整数 $x,c$，表示顶点 $x$ 上有一颗颜色为 $c$ 的棋子。其中 $c=0$ 表示一颗黑棋，$c=1$ 表示一颗白棋。\n\n接下来 $m$ 行每行三个整数 $u,v,w$，表示图中有一条连接 $u$ 和 $v$ 的权值为 $w$ 的边。\n\n## Output\n\n输出一行一个整数，为所求答案。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n对于第一组样例，可以选定顶点 $3$，然后将 $1$ 号点上的黑棋移动到顶点 $2$，将 $2$ 号点的黑棋移动到顶点 $3$，这样两颗棋子所在的顶点之间由一条边权为 $2$ 的边连接，产生的目数为 $2$。\n\n### 子任务\n\n对于所有测试数据，保证  $3 \\leq n \\leq 100$，$n-1 \\leq m \\leq \\frac{n(n-1)}{2}$，$1 \\leq k \\leq n-1$，$0 \\leq w_i \\leq 10^5$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5iu3ldkx.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9542","tags":["动态规划 DP","图论","2023","O2优化","二分图","Ad-hoc","湖北"],"sample_group":[["3 2 2\n1 0\n2 1\n1 2 1\n2 3 2\n","2"],["4 4 3\n1 1\n2 1\n3 0\n1 2 1\n2 3 1\n3 4 1\n4 1 3","3"],["见选手目录下的 alphago/alphago3.in 与 alphago/alphago3.ans。","见选手目录下的 alphago/alphago3.in 与 alphago/alphago3.ans。"],["见选手目录下的 alphago/alphago4.in 与 alphago/alphago4.ans。","见选手目录下的 alphago/alphago4.in 与 alphago/alphago4.ans。"],["见选手目录下的 alphago/alphago5.in 与 alphago/alphago5.ans。","见选手目录下的 alphago/alphago5.in 与 alphago/alphago5.ans。"]],"created_at":"2026-03-03 11:09:25"}}