hdu7298 Coin(网络流+按时间拆点)

**HDU7298 Coin**

**题目描述**

在一个名为"Coin"的游戏中，玩家可以购买、出售或交换硬币。每个硬币都有一个时间戳，表示它被创建的时间。玩家可以在某个时间点购买或出售硬币，但不能同时进行两种操作。

**题目要求**

给定一组硬币，每个硬币都有一个时间戳和一个价值。请问，在每个时间点结束时，玩家的总价值是多少？

**解决方案**

这个问题可以使用网络流来解决。我们首先建立一个图，其中每个时间点对应一个节点。然后，我们为每个硬币创建一个边，从其创建时间的节点到其价值的节点。

由于玩家不能同时进行两种操作，因此我们需要在图中添加一些限制。具体来说，我们需要将所有从某个时间点开始的边连接起来，以表示玩家只能在该时间点结束时进行一次操作。

**代码示例**

cpp#include <iostream>
#include <vector>

using namespace std;

const int N =100010;
typedef long long ll;

struct Edge {
 int to, next;
};

Edge edge[N << 1];
int head[N], tot;

void add(int u, int v) {
 edge[++tot].to = v;
 edge[tot].next = head[u];
 head[u] = tot;
}

ll dis[N];

bool spfa(int s, int t) {
 for (int i =1; i <= n; ++i)
 dis[i] = N;

 vector<int> q;
 q.push_back(s);
 dis[s] =0;

 while (!q.empty()) {
 int u = q.back();
 q.pop_back();

 for (int i = head[u]; i; i = edge[i].next) {
 int v = edge[i].to;
 if (dis[v] > dis[u] + w[i]) {
 dis[v] = dis[u] + w[i];
 if (!vis[v])
 q.push_back(v);
 }
 }
 }

 return dis[t] != N;
}

int main() {
 int n, m;

 cin >> n >> m;

 for (int i =1; i <= m; ++i) {
 int t, v;

 cin >> t >> v;

 add(t, v);
 }

 ll ans =0;

 for (int i =1; i <= n; ++i)
 if (spfa(i, n +1))
 ans += dis[n +1];

 cout << ans << endl;

 return0;
}