青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0
PIGS
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 10566Accepted: 4622

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs. 
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold. 
More precisely, the procedure is as following: the customer arives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses. 
An unlimited number of pigs can be placed in every pig-house. 
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N. 
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000. 
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line): 
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Sample Output

7


最大流,構(gòu)圖思想:用人當點,因為每個人是按順序的,所以第i個人第一次打開第k個豬圈,第j個人第二次打開第k個豬圈時,相當于第i個人向第j個人增流。
所以,如果第i個人持有第k個豬圈的鑰匙,如果是第一次打開,就從源點引邊向該點,邊權(quán)累加豬圈的值(一個人可能持有多個鑰匙,所以要累加),如果不是第一次,那么從上一次那個人引出一條無限大的邊到i點作為增流。每個點到匯點的權(quán)值是該人需要的個數(shù),最大流一次就行了。
SAP,時間很好看。
代碼:
#include<stdio.h>
#include<string.h>
#include
<iostream>
#include
<queue>
#define N 1010
using namespace std;
const int maxnode=60000;
const int maxedge=320000;
const int  inf = 1 << 30;
int S,T,cnt,n,m;
int head[maxnode],gap[maxnode],pre[maxnode],cur[maxnode],dis[maxnode];
struct Edge
{
    
int S,t;
    
int next;
    
int w;
}st[maxedge];
void init()
{
    memset(head,
-1,sizeof(head));
    cnt
=0;
}
void AddEdge(int S,int t,int w)
{
    st[cnt].S
=S;
    st[cnt].t
=t;
    st[cnt].w
=w;
    st[cnt].next
=head[S];
    head[S]
=cnt;
    cnt
++;
    st[cnt].S
=t;
    st[cnt].t
=S;
    st[cnt].w
=0;
    st[cnt].next
=head[t];
    head[t]
=cnt;
    cnt
++;
}
void bfs()
{
    memset(gap,
0,sizeof(gap));
    memset(dis,
-1,sizeof(dis));
    queue
<int >Q;
    Q.push(T);
    dis[T]
=0;
    gap[
0]=1;
    
int k,t;
    
while(!Q.empty())
    {
        k
=Q.front();
        Q.pop();
        
for(int i=head[k];i!=-1;i=st[i].next)
        {
            t
=st[i].t;
            
if(dis[t]==-1&&st[i^1].w>0)
            {
                dis[t]
=dis[k]+1;
                gap[dis[t]]
++;
                Q.push(t);
            }
        }
    }
}
int sap()
{
    
int i;
    
for( i=S;i<=T;i++)cur[i]=head[i];
    pre[S]
=S;
    
int u=S,v;
    
int  flow=0;
    
int aug=inf;
    
bool flag;
    
while(dis[S]<=T)
    {
        flag
=false;
        
for( i=cur[u];i!=-1;i=st[i].next)
        {
            v
=st[i].t;
            
if(st[i].w>0&&dis[u]==dis[v]+1)
            {
                cur[u]
=i;
                flag
=true;
                pre[v]
=u;
                aug
=(aug>st[i].w)?st[i].w:aug;
                u
=v;
                
if(v==T)
                {
                    flow
+=aug;
                    
for(u=pre[u];v!=S;u=pre[u])
                    {
                        v
=u;
                        st[cur[u]].w
-=aug;
                        st[cur[u]
^1].w+=aug;
                    }
                    aug
=inf;
                }
                
break;
            }
        }
        
if(flag==true)continue;
        
int mint=T;
        
for( i=head[u];i!=-1;i=st[i].next)
        {
            v
=st[i].t;
            
if(st[i].w>0&&mint>dis[v])
            {
                cur[u]
=i;
                mint
=dis[v];
            }
        }
        gap[dis[u]]
--;
        
if(gap[dis[u]]==0)break;
        gap[dis[u]
=mint+1]++;
        u
=pre[u];
        
if(u==S)aug=inf;
    }
    
return flow;
}

int main()
{
    
int map[N][N];
    
int num[N];
    
int f[N];
    
while (scanf("%d%d"&m, &n) != EOF)
    {
        memset(map, 
0sizeof(map));
        memset(f, 
0sizeof(f));
        init();
        S 
= 0;
        T 
= n + 1;
        
for (int i = 1; i <= m; ++i)
            scanf(
"%d"&num[i]);
        
for (int i = 1; i <= n; ++i)
        {
            
int a, b;
            scanf(
"%d"&a);
            
for (int j = 1; j <= a; ++j)
            {
                
int x;
                scanf(
"%d"&x);
                
if (f[x] == 0)
                {
                    map[S][i] 
+= num[x];
                    f[x] 
= i;
                }
                
else
                {
                    map[f[x]][i] 
= inf;
                    f[x] 
= i;
                }
            }
            scanf(
"%d"&b);
            map[i][T] 
+= b;
        }
        
for (int i = S; i <= T; ++i)
            
for (int j = S; j <= T; ++j)
            
if (map[i][j])
            {
                
//printf("%d %d %d\n", i, j, map[i][j]);
                AddEdge(i, j, map[i][j]);
            }
        bfs();
        printf(
"%d\n", sap());
    }
}

/*
4 2
1 2 3 5
3 1 2 3 10
1 4 5

*/
posted on 2011-10-15 22:12 LLawliet 閱讀(174) 評論(0)  編輯 收藏 引用 所屬分類: 網(wǎng)絡流
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            一本色道久久88综合日韩精品| 欧美阿v一级看视频| 亚洲精品乱码久久久久久黑人| 久久蜜臀精品av| 亚洲国产婷婷综合在线精品 | 国产欧美日韩精品a在线观看| 亚洲欧美成人精品| 香蕉久久夜色精品| 影音先锋中文字幕一区二区| 欧美激情第4页| 欧美日韩国产黄| 久久久夜精品| 欧美日韩不卡合集视频| 欧美一区二区三区视频| 久久乐国产精品| 亚洲午夜av在线| 欧美中文字幕视频| 一区二区三区回区在观看免费视频| 亚洲嫩草精品久久| 最新国产乱人伦偷精品免费网站| 夜夜嗨av色综合久久久综合网| 国精品一区二区三区| 亚洲国产精品精华液2区45| 国产精品久久久久久久久久ktv| 久久久久久午夜| 欧美日韩一区二区欧美激情 | 午夜视频一区| 欧美高清视频一区二区| 欧美在线不卡视频| 欧美精品 国产精品| 久久久久国色av免费观看性色| 欧美激情bt| 狂野欧美性猛交xxxx巴西| 欧美视频一区| 欧美激情在线狂野欧美精品| 国产伦精品一区二区三区在线观看| 欧美韩国日本一区| 国产一区成人| 亚洲永久免费视频| 亚洲私人影院在线观看| 欧美成人国产一区二区| 蜜月aⅴ免费一区二区三区| 国产精品私拍pans大尺度在线 | 亚洲午夜免费福利视频| 欧美大胆人体视频| 免费成人激情视频| 好吊妞**欧美| 欧美自拍偷拍| 久久精品国产欧美亚洲人人爽| 国产精品成人aaaaa网站| 亚洲欧洲精品一区二区三区| 伊人伊人伊人久久| 久久国产天堂福利天堂| 久久精品国内一区二区三区| 国产精品日韩专区| 亚洲欧美一区二区三区在线 | 亚洲国产高清在线| 狼狼综合久久久久综合网| 久久综合精品一区| 黄色一区二区三区四区| 久久精品久久99精品久久| 久久九九久久九九| 一区二区在线视频| 久久综合给合| 亚洲国产老妈| 99国产欧美久久久精品| 欧美精品午夜| 亚洲天堂成人| 久久精品91久久香蕉加勒比| 国产色综合久久| 久久久久亚洲综合| 欧美激情一区二区三区不卡| 亚洲裸体视频| 国产精品黄视频| 性欧美超级视频| 蜜桃久久精品一区二区| 亚洲精品少妇30p| 欧美先锋影音| 久久久.com| 亚洲国产一二三| 亚洲欧美日韩成人| 狠狠色丁香久久婷婷综合_中| 久久久国产视频91| 亚洲精品国产精品国自产在线 | 亚洲日本免费电影| 亚洲欧美怡红院| 经典三级久久| 欧美日韩高清在线一区| 亚洲欧美激情视频在线观看一区二区三区| 久久av资源网| 亚洲美女性视频| 国产精品综合视频| 免费在线成人av| 亚洲一区自拍| 亚洲国产1区| 欧美在线地址| av成人免费在线| 韩国三级电影久久久久久| 欧美精品亚洲二区| 欧美专区日韩视频| 一区二区三区**美女毛片| 久久久一区二区三区| 一区二区三区精品视频在线观看 | 欧美日韩另类国产亚洲欧美一级| 亚洲免费小视频| 91久久精品www人人做人人爽| 欧美一级播放| 夜色激情一区二区| 亚洲福利视频网| 国产欧美 在线欧美| 欧美激情在线狂野欧美精品| 欧美一区二区在线看| 9l视频自拍蝌蚪9l视频成人| 美国三级日本三级久久99| 午夜精品国产| 亚洲私人影院在线观看| 91久久线看在观草草青青| 国产一区在线视频| 国产精品色婷婷| 欧美日韩中字| 欧美激情精品久久久久久免费印度| 欧美一区二区久久久| 亚洲一区二区成人在线观看| 欧美激情一区二区三区蜜桃视频| 久久综合图片| 久久亚洲精品一区二区| 久久爱91午夜羞羞| 午夜精品美女自拍福到在线| 亚洲午夜91| 亚洲免费视频观看| 中国av一区| 一区二区三区日韩精品视频| 亚洲精品一区二区网址| 亚洲人成网站在线观看播放| 在线电影欧美日韩一区二区私密| 国产视频一区在线观看一区免费| 国产精品国码视频| 国产精品男女猛烈高潮激情| 国产精品国产自产拍高清av王其| 欧美日韩视频在线一区二区观看视频| 欧美a级大片| 欧美日本国产一区| 欧美日韩激情小视频| 欧美性猛片xxxx免费看久爱| 欧美性大战久久久久久久蜜臀| 欧美日韩在线视频观看| 欧美亚一区二区| 国产精品手机视频| 国产午夜精品全部视频在线播放 | 欧美精选午夜久久久乱码6080| 欧美精品在线免费播放| 欧美午夜精品理论片a级按摩| 国产精品高潮视频| 国产视频一区欧美| 亚洲国产精品久久久| 99热这里只有成人精品国产| 亚洲一级片在线看| 久久国产精品72免费观看| 老司机亚洲精品| 亚洲精品免费网站| 亚洲欧美另类久久久精品2019| 欧美一区二区视频97| 美女性感视频久久久| 欧美日韩伦理在线免费| 国产日韩高清一区二区三区在线| 国产在线观看精品一区二区三区| 亚洲福利国产| 亚洲欧美在线aaa| 狂野欧美一区| 99这里只有久久精品视频| 亚洲欧美综合v| 欧美成人精品三级在线观看| 国产精品国产| 91久久香蕉国产日韩欧美9色| 亚洲小视频在线观看| 免费不卡亚洲欧美| 一区二区三区日韩| 免费成人性网站| 国产美女诱惑一区二区| 亚洲国产精品ⅴa在线观看| 亚洲欧美成人一区二区在线电影| 久久综合狠狠综合久久综合88 | 欧美影院成年免费版| 亚洲高清网站| 欧美一级欧美一级在线播放| 欧美喷水视频| 亚洲电影免费观看高清完整版在线观看| 艳女tv在线观看国产一区| 免费看精品久久片| 亚洲曰本av电影| 欧美日韩亚洲一区三区| 亚洲激情女人| 狂野欧美一区| 午夜精品视频在线观看| 欧美视频观看一区| 亚洲欧洲日产国码二区| 久久综合五月| 欧美亚洲视频一区二区| 国产精品久久久久久久午夜| 一区二区毛片|