ZOJ 3229 Shoot the Bullet

ZOJ 3229 Shoot the Bullet

有源點匯點的上下界最大流問題。。。

建圖很簡單。。。按題意即可。。。

設原圖 源點為 s 匯點 為 t，連一條t到s無下界上界無限大的邊。。。。設兩個超級源S，T，像無源匯判斷可行流的問題一樣，記錄每個點的in，連接到相應的超級源匯點。。。對S，T跑一遍最大流，並檢測S所連邊是否滿流。。。如果不滿足連可行流都沒有無解。。。否則去掉S，T點（但總點數不要邊。。。在這裡錯了一下午）對s，t跑一遍最大流。得到的結果既答案。。。。。第一遍最大流保證了每個點的下界流得到滿足，此時的圖裡還有很多自由流可以走，第二遍最大流就將這些流走滿了得到的就是答案。。。

總結一下有源點匯點的上下界最大流 步驟為：

1：連接 t-->s INF，並增加S，T 像無源匯可行流一樣建邊，第一次最大流判斷可行流

2：去掉S，T（Adj變-1） 總點數不變，第二次最大流得到答案

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 beautifuldanmaku(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!

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+RHVyaW5nIHRoZSBjb21pbmcgPGVtPm48L2VtPiBkYXlzLCBBeWEgaXMgcGxhbm5pbmcgdG8gdGFrZSBtYW55IHBob3RvcyBvZiA8ZW0+bTwvZW0+IGN1dGUgZ2lybHMgbGl2aW5nIGluIDxlbT5HZW5zb2t5bzwvZW0+IHRvIHdyaXRlIEJ1bmJ1bm1hcnUgTmV3cyBkYWlseSBhbmQgcmVjb3JkIGF0IGxlYXN0IDxlbT5HPHN1Yj54PC9zdWI+PC9lbT4gcGhvdG9zCiBvZiBnaXJsIDxlbT54PC9lbT4gaW4gdG90YWwgaW4gdGhlIDxlbT5CdW5rYWNob3U8L2VtPi4gQXQgdGhlIDxlbT5rPC9lbT4tdGggZGF5LCB0aGVyZSBhcmUgPGVtPkM8c3ViPms8L3N1Yj48L2VtPiB0YXJnZXRzLCA8ZW0+VDxzdWI+azE8L3N1Yj48L2VtPiwgPGVtPlQ8c3ViPmsyPC9zdWI+PC9lbT4sIC4uLiwgPGVtPlQ8c3ViPmtDPHN1Yj5rPC9zdWI+PC9zdWI+PC9lbT4uIFRoZSBudW1iZXIgb2YgcGhvdG9zIG9mIHRhcmdldCA8ZW0+VDxzdWI+a2k8L3N1Yj48L2VtPiB0aGF0CiBBeWEgdGFrZXMgc2hvdWxkIGJlIGluIHJhbmdlIFs8ZW0+TDxzdWI+a2k8L3N1Yj48L2VtPiwgPGVtPlI8c3ViPmtpPC9zdWI+PC9lbT5dLCBpZiBsZXNzLCBBeWEgY2Fubm90IHdyaXRlIGFuIGludGVyZXN0aW5nIGFydGljbGUsIGlmIG1vcmUsIHRoZSBnaXJsIHdpbGwgYmVjb21lIGFuZ3J5IGFuZCB1c2UgaGVyIDxlbT5sYXN0IHNwZWxsIGNhcmQ8L2VtPiB0byBhdHRhY2sgQXlhLiBXaGF0"s more, Aya cannot take more than D_k 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, G₁, G₂, ..., G_m 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

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 3 9
1 3 9
2 3 9

2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 0 3
1 3 6
2 6 9

2 3
12 12 12
3 15
0 3 9
1 3 9
2 3 9
3 21
0 0 3
1 3 6
2 6 12

Sample Output

36
6
6
6
6
6
6

36
9
6
3
3
6
9

-1

External Links

Wikipedia
Touhou Wiki

#include 
#include 
#include 
#include 

using namespace std;

const int maxn=2222;
const int maxm=1000000;
const int INF=0x3f3f3f3f;

struct Edge
{
    int to,next,cap,flow;
}edge[maxm];

int Size,Adj[maxn];
int gap[maxn],dep[maxn],pre[maxn],cur[maxn];

void init()
{
    Size=0;
    memset(Adj,-1,sizeof(Adj));
}

void addedge(int u,int v,int w,int rw=0)
{
    edge[Size].to=v; edge[Size].cap=w; edge[Size].next=Adj[u];
    edge[Size].flow=0; Adj[u]=Size++;
    edge[Size].to=u; edge[Size].cap=rw; edge[Size].next=Adj[v];
    edge[Size].flow=0; Adj[v]=Size++;
}

int sap(int start,int end,int N)
{
    memset(gap,0,sizeof(gap));
    memset(dep,0,sizeof(dep));
    memcpy(cur,Adj,sizeof(Adj));
    
    int u=start;
    pre[u]=-1; gap[0]=N;
    int ans=0;
    
    while(dep[start]edge[i].cap-edge[i].flow)
                    Min=edge[i].cap-edge[i].flow;
            for(int i=pre[u];~i;i=pre[edge[i^1].to])
            {
                edge[i].flow+=Min;
                edge[i^1].flow-=Min;
            }
            u=start;
            ans+=Min;
            continue;
        }
        bool flag=false;
        int v;
        for(int i=cur[u];~i;i=edge[i].next)
        {
            v=edge[i].to;
            if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u])
            {
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
        }
        if(flag)
        {
            u=v;
            continue;
        }
        int Min=N;
        for(int i=Adj[u];~i;i=edge[i].next)
            if(edge[i].cap-edge[i].flow&&dep[edge[i].to]0)
            {
                sum+=in[i];
                addedge(n+m+2,i,in[i]);
            }
        }
        int MaxFlow=sap(n+m+2,n+m+3,n+m+4);
        if(MaxFlow!=sum) puts("-1");
        else
        {
            Adj[n+m+2]=Adj[n+m+3]=-1;
            MaxFlow=sap(0,n+m+1,n+m+4);
            printf("%d\n",MaxFlow);
            for(int i=0;i