题意：给一个有N个点的无向图，要求从1向N传送一定的数据，每条边的容量是一定的，如果能做到，输出最小的费用，否则输出Impossible.
解析：由于是无向图，所以每个有连接的两个点要建4条边，分别是edge(from,to,cap,0,cost),edge(to,from,0,0,-cost),edge(to,from,cap,0,cost),edge(from,to,0,0,-cost)
设置一个起点0,0与1连一条有向边，容量为题目给出的D，这样限制了最大的流量，如果最后的流量不等于D，则是Impossible.否则输出最小费。
代码如下:
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<iterator>
#include<utility>
#include<sstream>
#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
const double eps=0.00000001;
typedef long long LL;
const LL INF=1ll<<60;
const int maxn=105;
const int maxm=5005;
const int skip=10010;
int N,M;
LL D,K;
int u[maxm],v[maxm];
LL waste[maxm];
struct edge
{
int from,to;
LL cap;
LL flow,cost;
edge(int from=0,int to=0,LL cap=0,LL flow=0,LL cost=0)
:from(from),to(to),cap(cap),flow(flow),cost(cost){}
}save[4*maxm];
int edge_num;
vector<int> G[maxn];
void addedge(int from,int to,LL cap,LL cost)
{
int a=edge_num++; // 增加4条边，编号分别是a,b,sa,sb,skip的目的是为了把一条无向边分隔开，
int b=edge_num++; // 因为如果其中一条有向边的flow改变了，另一条边也要改变
int sa=a+skip;
int sb=b+skip;
save[a]=edge(from,to,cap,0,cost);
save[b]=edge(to,from,0,0,-cost);
save[sa]=edge(to,from,cap,0,cost);
save[sb]=edge(from,to,0,0,-cost);
G[from].push_back(a); G[from].push_back(sb); // 建立临接表
G[to].push_back(b); G[to].push_back(sa);
}
LL add[maxn],C[maxn]; // add[]是增加的流量
int fa[maxn]; // 保存父亲边编号
bool inq[maxn]; // 入队标记
inline void init(int be) // 初始化
{
memset(add,0,sizeof(add));
memset(inq,false,sizeof(inq));
add[be]=INF;
fa[be]=0;
inq[be]=true;
for(int i=0;i<=N;i++) C[i]=INF;
C[be]=0;
}
void MFMC(int be,int en)
{
LL cnt=0;
LL ret=0; // cnt是最大流量，ret是最小费用
while(true)
{
init(be);
queue<int> que;
que.push(be);
while(!que.empty())
{
int from=que.front(); que.pop();
inq[from]=false; // spfa跑最小费，入队标记改为false
for(int i=0;i<G[from].size();i++)
{
int edge_id=G[from][i];
edge& e=save[edge_id];
int to=e.to;
LL cap=e.cap,flow=e.flow,cost=e.cost;
if(cap>flow&&C[to]>C[from]+cost) //更新
{
C[to]=C[from]+cost;
fa[to]=edge_id; // 保存编号
add[to]=min(add[from],cap-flow);
if(!inq[to]){ inq[to]=true; que.push(to); } //入队
}
}
}
if(!add[en]) break;
cnt+=add[en];
ret+=add[en]*C[en];
for(int st=en;st!=be;st=save[fa[st]].from) // 往回找
{
int a=fa[st],b=fa[st]^1; // 修改4条边
int sa,sb;
if(a<skip) { sa=a+skip;sb=sa^1; }
else { sa=a-skip; sb=sa^1; }
save[a].flow+=add[en];
save[b].flow-=add[en];
save[sa].flow-=add[en];
save[sb].flow+=add[en];
}
}
if(cnt==D) printf("%lld\n",ret);
else printf("Impossible.\n");
}
int main()
{
while(cin>>N>>M)
{
for(int i=0;i<maxn;i++) G[i].clear();
for(int i=1;i<=M;i++) scanf("%d%d%lld",&u[i],&v[i],&waste[i]);
scanf("%lld%lld",&D,&K);
save[0]=edge(0,1,D,0,0); // 建立0到1的边
save[1]=edge(1,0,0,0,0);
G[0].push_back(0);
G[1].push_back(1);
edge_num=2;
for(int i=1;i<=M;i++) addedge(u[i],v[i],K,waste[i]); // 增加边
MFMC(0,N);
}
return 0;
}