有源汇的上下界网络流求最小流。
这个其实和上道题差不多……题目描述我没怎么看明白……好像就是让你按照他说的把图建出来就行了，注意这个题的字符处理，可能有长度大于1的字符串，要注意一下。求最小流的话还是先求可行流，之后因为可行流可能流多，而从汇点向原点跑相当于退流。所以我们再从原点向汇点跑一次最大流，两次结果相减就是答案。
然后这个题其实挺奇怪的……辅助源汇点连接的边其实删不删无所谓，HDU的数据不知道行不行……然而POJ这题没数据，交个空程序就能过……
看一下代码。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;
const int M = 40005;
const int N = 100005;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
int read()
{
int ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
struct edge
{
int next,to,from,v;
}e[N<<3];
int head[N],cur[N],deg[N],x,y,z,n,m,g,ecnt,S,T,S1,T1,c,d,tot;
int low[2005][2005],dep[N],sta[N],top;
queue <int> q;
char s[3];
void add(int x,int y,int z)
{
e[++ecnt].to = y;
e[ecnt].next = head[x];
e[ecnt].v = z;
head[x] = ecnt;
}
void clear()
{
memset(head,-1,sizeof(head)),ecnt = -1,tot = 0;
memset(deg,0,sizeof(deg));
}
bool bfs(int s,int t)
{
while(!q.empty()) q.pop();
rep(i,0,t) cur[i] = head[i];
memset(dep,-1,sizeof(dep));
dep[s] = 0,q.push(s);
while(!q.empty())
{
int k = q.front();q.pop();
for(int i = head[k];~i;i = e[i].next)
{
if(e[i].v && dep[e[i].to] == -1)
dep[e[i].to] = dep[k] + 1,q.push(e[i].to);
}
}
return dep[t] != -1;
}
int dfs(int s,int t,int lim)
{
if(s == t || !lim) return lim;
int flow = 0;
for(int i = cur[s];~i;i = e[i].next)
{
cur[s] = i;
if(dep[e[i].to] != dep[s] + 1) continue;
int f = dfs(e[i].to,t,min(lim,e[i].v));
if(f)
{
e[i].v -= f,e[i^1].v += f;
flow += f,lim -= f;
if(!lim) break;
}
}
if(!flow) dep[s] = -1;
return flow;
}
int dinic(int s,int t)
{
int maxflow = 0;
while(bfs(s,t)) maxflow += dfs(s,t,INF);
return maxflow;
}
int change(char *c)
{
if(c[0] == '+') return S;
if(c[0] == '-') return T;
int l = strlen(c),cur = 0;
rep(i,0,l-1) cur *= 10,cur += c[i] - '0';
return cur;
}
void rebuild()
{
e[ecnt].v = e[ecnt-1].v = 0;
//for(int i = head[S1];~i;i = e[i].next) e[i].v = e[i^1].v = 0;
//for(int i = head[T1];~i;i = e[i].next) e[i].v = e[i^1].v = 0;
}
int main()
{
//freopen("f.in","r",stdin);
//freopen("f.out","w",stdout);
while(scanf("%d%d",&n,&m))
{
if(!n && !m) break;
T = n + 1,S1 = T + 1,T1 = S1 + 1;
clear();
rep(i,1,m)
{
scanf("%s",s),x = change(s);
scanf("%s",s),y = change(s);
z = read(),add(x,y,INF-z),add(y,x,0),deg[x] += z,deg[y] -= z;
}
rep(i,S,T)
{
if(deg[i] > 0) add(i,T1,deg[i]),add(T1,i,0),tot += deg[i];
else add(S1,i,-deg[i]),add(i,S1,0);
}
add(T,S,INF),add(S,T,0);
int g = dinic(S1,T1);
if(g != tot) {printf("impossible\n");continue;}
g = e[ecnt].v,rebuild();
printf("%d\n",g - dinic(T,S));
}
return 0;
}