# HDU 6118 度度熊的交易计划 （最小费用最大流）

## Input

1<=n<=500,

1<=m<=1000,

1<=a[i],b[i],c[i],d[i],k[i]<=1000,

1<=u[i],v[i]<=n

## Sample Input

2 1
5 5 6 1
3 5 7 7
1 2 1


## Sample Output

23


## AC 代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

typedef long long LL;

const int M=2010;
const int N=510;

struct edge
{
int to;
int next;
int cap;
int cost;
} e[11000];

int d[N], pre[N], path[N];
bool vis[N];

void init()
{
tot = 0;
}

void addedge(int s, int t, int cap, int cost)
{
e[tot].to=t;
e[tot].cap=cap;
e[tot].cost=cost;
e[tot].to=s;
e[tot].cap=0;
e[tot].cost=-cost;
}

int spfa(int s, int t)
{
memset(d,-INF,sizeof(d));
memset(pre,-1,sizeof(pre));
memset(path,-1,sizeof(path));
memset(vis,false,sizeof(vis));
int res = d[0];
d[s] = 0;
vis[s] = true;
queue<int>q;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if (d[v] < d[u] + e[i].cost && e[i].cap > 0)
{
d[v] = d[u] + e[i].cost;
pre[v] = u;
path[v] = i;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
return d[t] != res;
}

int MinCostMaxFlow(int s, int t,int &cost)
{
int flow;
flow=cost=0;
while (spfa(s, t))
{
int minn = INF;
for (int i = t; i != s && ~i; i = pre[i])
minn = min(minn, e[path[i]].cap);
for (int i = t; i != s && ~i; i = pre[i])
{
e[path[i]].cap -= minn;
e[path[i] ^ 1].cap += minn;
}
if (d[t] < 0)
break;
flow += minn;
cost += minn * d[t];
}
return flow;
}

int main(void)
{
int n,m;
while (cin>>n>>m)
{
init();
int s=0,t=n+1,cost;
for (int i=1; i<=n; i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
}
while (m--)
{
int u,v,k;
cin>>u>>v>>k;