UVa 10594 Data Flow / 最小费用最大流

注意long long会溢出 取一个源点0保证流出的流量是D 如果最大流是D 说明可行

#include 
#include 
#include 
using namespace std;
const int MAX = 110;
const long long fd = 1;
const long long INF = fd << 60;
int n,m;
struct edge
{
int u;
int v;
long long cost;
int flow;
int cap;
int next;
}e[50000];

struct node
{
int u;
int v;
int w;
}E[5050];
long long dis[MAX];
int first[MAX];
int p[MAX];
bool vis[MAX];
int edgenum;
int f,d,cap;
long long c;
void add(int u,int v,long long w,int num)
{
e[edgenum].u = u;
e[edgenum].v = v;
e[edgenum].cap = num;
e[edgenum].cost = w;
e[edgenum].flow = 0;
e[edgenum].next = first[u];
first[u] = edgenum++;
e[edgenum].u = v;
e[edgenum].v = u;
e[edgenum].cap = 0;
e[edgenum].cost = -w;
e[edgenum].flow = 0;
e[edgenum].next = first[v];
first[v] = edgenum++;
}
void EK()
{
queue  q;
c = f = 0;
while(1)
{
for(int i = 0;i <= n; i++)
dis[i] = (i == 0 ? 0 : INF);
memset(vis,false,sizeof(vis));
memset(p,-1,sizeof(p));
q.push(0);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int k = first[u]; k != -1; k = e[k].next)
{
int v = e[k].v;
if(e[k].cap > e[k].flow && dis[v] > dis[u] + e[k].cost)
{
dis[v] = dis[u] + e[k].cost;
p[v] = k;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(dis[n] == INF)
break;
int a = 999999999;
for(int u = p[n]; u != -1; u = p[e[u].u])
a = min(a,e[u].cap - e[u].flow);
for(int u = p[n]; u != -1; u = p[e[u].u])
{
e[u].flow += a;
e[u^1].flow -= a;
}
c += dis[n] * a;
f += a;
}
}
int main()
{
int i,j;
while(scanf("%d %d",&n,&m)!=EOF)
{
edgenum = 0;
memset(first,-1,sizeof(first));
for(i = 0;i < m; i++)
{
scanf("%d %d %lld",&E[i].u,&E[i].v,&E[i].w);
}
scanf("%d %d",&d,&cap);
add(0,1,0,d);
for(i = 0; i < m; i++)
{
add(E[i].u,E[i].v,E[i].w,cap);
add(E[i].v,E[i].u,E[i].w,cap);
}
EK();
if(f == d)
printf("%lld\n",c);
else
printf("Impossible.\n");
}
return 0;
}
/*
4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 100
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 1
*/