ZOJ 3229 Shoot the Bullet(有源汇上下界网络流)

程序员文章站 2022-06-10 14:42:59

...

Shoot the Bullet

Time Limit: 2 Seconds Memory Limit: 32768 KB Special Judge

Gensokyo is a world which exists quietly beside ours, separated by a mystical border. It is a utopia where humans and other beings such as fairies, youkai(phantoms), and gods live peacefully together. Shameimaru Aya is a crow tengu with the ability to manipulate wind who has been in Gensokyo for over 1000 years. She runs the Bunbunmaru News - a newspaper chock-full of rumors, and owns the Bunkachou - her record of interesting observations for Bunbunmaru News articles and pictures of beautiful danmaku(barrange) or cute girls living in Gensokyo. She is the biggest connoisseur of rumors about the girls of Gensokyo among the tengu. Her intelligence gathering abilities are the best in Gensokyo!

ZOJ 3229 Shoot the Bullet(有源汇上下界网络流)

During the coming n days, Aya is planning to take many photos of m cute girls living in Gensokyo to write Bunbunmaru News daily and record at least Gx photos of girl x in total in the Bunkachou. At the k-th day, there are Ck targets, Tk1, Tk2, ..., TkCk. The number of photos of target Tki that Aya takes should be in range [Lki, Rki], if less, Aya cannot write an interesting article, if more, the girl will become angry and use her last spell card to attack Aya. What's more, Aya cannot take more than Dk photos at the k-th day. Under these constraints, the more photos, the better.

Aya is not good at solving this complex problem. So she comes to you, an earthling, for help.

Input

There are about 40 cases. Process to the end of file.

Each case begins with two integers 1 <= n <= 365, 1 <= m <= 1000. Then m integers, G1, G2, ..., Gm in range [0, 10000]. Then n days. Each day begins with two integer 1 <= C <= 100, 0 <= D <= 30000. Then C different targets. Each target is described by three integers, 0 <= T < m, 0 <= L <= R <= 100.

Output

For each case, first output the number of photos Aya can take, -1 if it's impossible to satisfy her needing. If there is a best strategy, output the number of photos of each girl Aya should take at each day on separate lines. The output must be in the same order as the input. If there are more than one best strategy, any one will be OK.

Output a blank line after each case.

Sample Input

Sample Output

36
6
6
6
6
6
6

36
9
6
3
3
6
9

-1
建立源汇点S，T，把天数当作左部分的点，女神当作右部分的点，S与左部分的点连接下界为0，上界为Di的边，右部分的点与T连接下界为Gi，上界为无穷大的边，天数和女神之间连接对应上界为Ri，下界为Li的边，然后在添加边T-〉S，流量为无穷大，这样就转化为无源汇上下界网络流问题，可参考：https://blog.csdn.net/GYH0730/article/details/82591983，判断是否有可行流，如果存在可行流，再在残余网络里从S到T跑一遍最大流，所有起点为S的边的流量和为总的拍照数目，左边点与右边点连接的边的流量为对应的每天给每个女神的拍照数目

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 110005;
const int INF = 0x3f3f3f3f;
struct Edge1
{
	int from,to,cap,flow;
};
struct Dinic
{
	int n,m,s,t;
	vector<Edge1> edges;
	vector<int> G[MAXN];
	bool vis[MAXN];
	int d[MAXN];
	int cur[MAXN];
	void init(int n)
	{
		this -> n = n;
		for(int i = 0; i <= n + 1; i++){
			G[i].clear();
		}
		edges.clear();
	}
	void AddEdge(int from,int to,int cap)
	{
		edges.push_back((Edge1){from,to,cap,0});
		edges.push_back((Edge1){to,from,0,0});
		m = edges.size();
		G[from].push_back(m - 2);
		G[to].push_back(m - 1);
	}
	bool BFS()
	{
		memset(vis,0,sizeof(vis));
		queue<int> Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = 1;
		while(!Q.empty()) {
			int x = Q.front();
			Q.pop();
			for(int i = 0; i < G[x].size(); i++) {
				Edge1& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow) {
					vis[e.to] = 1;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int DFS(int x,int a)
	{
		if(x == t || a == 0) return a;
		int flow = 0,f;
		for(int& i = cur[x]; i < G[x].size(); i++) {
			Edge1& e = edges[G[x][i]];
			if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0) {
				e.flow += f;
				edges[G[x][i] ^ 1].flow -= f;
				flow += f;
				a -= f;
				if(a == 0) break;
			}
		}
		return flow;
	}
	int Maxflow(int s,int t) {
		this -> s = s,this -> t = t;
		int flow = 0;
		while(BFS()) {
			memset(cur,0,sizeof(cur));
			flow += DFS(s,INF);
		}
		return flow;
	}
}din;
int n,m,S,T,SS,TT,temp,cnt,id,r,ans;
int in[MAXN],out[MAXN],low[MAXN],day[MAXN];
bool check()
{
    for(int i = S; i <= T; i++) {
        din.AddEdge(SS,i,in[i]);
        din.AddEdge(i,TT,out[i]);
    }
    din.Maxflow(SS,TT);
    for(int i = 0; i < din.edges.size(); i++) {
        Edge1 e = din.edges[i];
        if( (e.from == SS || e.to == TT) && (e.cap != e.flow) ) {
            return false;
        }
    }
    return true;
}
int main(void)
{
    while(scanf("%d %d",&n,&m) != EOF) {
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        S = 0,T = n + m + 1;
        SS = n + m + 2,TT = n + m + 3;
        din.init(n + m + 4);
        for(int i = 1; i <= m; i++) {
            scanf("%d",&temp);
            in[T] += temp;
            out[i + n] += temp;
        }
        cnt = 1;
        for(int i = 1; i <= n; i++) {
            scanf("%d %d",&temp,&day[i]);
            for(int j = 1; j <= temp; j++) {
                scanf("%d %d %d",&id,&low[cnt],&r);
                din.AddEdge(i,id + n + 1,r - low[cnt]);
                in[id + n + 1] += low[cnt];
                out[i] += low[cnt];
                cnt++;
            }
        }
        for(int i = 1; i <= n; i++) din.AddEdge(S,i,day[i]);
        for(int i = 1; i <= m; i++) din.AddEdge(i + n,T,INF);
        din.AddEdge(T,S,INF);
        if(check()) {
            din.Maxflow(S,T);
            ans = 0;
            for(int i = 0; i < din.edges.size(); i++) {
                Edge1 e = din.edges[i];
                if(e.from == S) ans += e.flow;
            }
            printf("%d\n",ans);
            for(int i = 1; i <= cnt - 1; i++) {
                printf("%d\n",din.edges[i * 2 - 2].flow + low[i]);
            }

        }
        else printf("-1\n");
        printf("\n");
    }
    return 0;
}