P1251 餐巾计划问题

因为脏的衣服在一天结束时才会有，干净的一天开始才会有，考虑拆点。

再考虑干净的衣服都是要被收集起来的，所以干净的要流向超汇。而脏的衣服可以从超源免费获得所需要的个数，而干净的衣服只能购买。

看张图吧，假如只有 1 个点的话，且需要无限多的衣服。

显然前者正确，后者矛盾（收集了脏衣服）

再者，这种建图会无法收集到当天的脏衣服。

假如从 T 点再回来也不现实，所以只能从 S 供给了。

因为最后一定满流，所以从 S 供给脏衣服是正确的。

#include 
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

#define int long long
#define N (int)(4e4+5)
#define inf (int)(2e18)
struct edge {
	int nex,to,w,c;
}e[N<<1];
int hea[N],cnt=1;
int n,S,T,ans;

void add_edge(int x,int y,int z,int c) {
	e[++cnt].nex=hea[x]; e[cnt].to=y; e[cnt].w=z; e[cnt].c=c; hea[x]=cnt;
}

void add(int x,int y,int z,int c) {
	add_edge(x,y,z,c);
	add_edge(y,x,0,-c);
}

dequeq;
bool vis[N];
int dis[N];
bool spfa() {
	for(int i=0;idis[x]+e[i].c) {
				dis[y]=dis[x]+e[i].c;
				if(!vis[y]) {
					vis[y]=1;
					if(!q.empty()&&dis[y]