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

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>
            亚洲精品视频在线播放| 蜜桃精品一区二区三区| 妖精成人www高清在线观看| 欧美激情国产日韩| 99国产一区| 亚洲素人在线| 国内精品视频在线观看| 欧美成va人片在线观看| 欧美久久综合| 久久国产视频网| 欧美a一区二区| 亚洲男女自偷自拍| 久久国产福利国产秒拍| 亚洲国产精品传媒在线观看| 亚洲欧洲综合另类| 欧美午夜宅男影院| 欧美国产三级| 午夜在线一区二区| 久久免费视频网| 亚洲图片在线观看| 久久国产福利| 亚洲制服少妇| 另类尿喷潮videofree| 亚洲一级二级| 蜜桃伊人久久| 久久久久国产精品麻豆ai换脸| 欧美成人免费在线| 久久精品国产亚洲一区二区| 能在线观看的日韩av| 久久国产精品黑丝| 欧美精品一区二区三区在线看午夜| 先锋影音久久久| 欧美日韩精品在线播放| 久久久亚洲一区| 国产精品www.| 亚洲精品国产拍免费91在线| 国产一区二区三区精品欧美日韩一区二区三区 | 欧美黑人在线观看| 久久久亚洲国产天美传媒修理工| 欧美美女bbbb| 亚洲电影免费观看高清| 国产在线乱码一区二区三区| 一区二区欧美日韩| 99www免费人成精品| 久久精品一级爱片| 欧美影院久久久| 国产精品超碰97尤物18| 欧美国产日韩xxxxx| 国产午夜精品一区理论片飘花| 亚洲日本无吗高清不卡| 在线欧美影院| 久久日韩精品| 久久亚洲午夜电影| 国产日韩综合一区二区性色av| 一区二区三区.www| 亚洲中字黄色| 国产精品二区在线观看| 一本色道久久综合亚洲精品按摩 | 国产精品一区二区在线观看不卡 | 亚洲国产成人一区| 亚洲欧洲精品一区二区三区| 久久久精品国产99久久精品芒果| 欧美在线免费观看| 国产欧美日韩亚洲精品| 亚洲综合欧美日韩| 久久成人18免费网站| 国产美女精品人人做人人爽| 亚洲一区二区成人| 欧美夜福利tv在线| 国产偷自视频区视频一区二区| 亚洲在线一区| 久久精品日产第一区二区| 国产一区二区三区黄| 久久亚洲春色中文字幕| 欧美成人自拍视频| av成人国产| 国产精品久久久久久影视| 午夜在线观看免费一区| 久久久亚洲精品一区二区三区 | 欧美日韩一区二区三区免费看| 一区二区三区福利| 久久国产福利| 亚洲高清视频的网址| 欧美久久影院| 香蕉成人久久| 亚洲国产一区二区三区高清| 中文亚洲欧美| 国产午夜精品美女视频明星a级| 久久精品国产第一区二区三区| 欧美91视频| 在线一区日本视频| 国产一区二区三区高清在线观看 | 一区二区av在线| 麻豆91精品| 亚洲少妇最新在线视频| 国产欧美日韩另类一区| 久久一二三区| 亚洲网在线观看| 欧美成人一区二区三区| 亚洲一区二区毛片| 激情视频一区二区三区| 欧美+亚洲+精品+三区| 亚洲图片在区色| 亚洲国产高清在线观看视频| 欧美日韩在线三区| 久久亚洲综合色| 亚洲中无吗在线| 亚洲精品国产系列| 久久精品视频一| 亚洲欧美不卡| 一本色道久久综合精品竹菊 | 国产一区二区三区免费在线观看 | 亚洲一本大道在线| 最新中文字幕亚洲| 老司机免费视频一区二区三区| 一区二区三区www| 亚洲国产精品va在线看黑人动漫| 国产精品a久久久久久| 免费观看欧美在线视频的网站| 亚洲欧美日韩区| 一本大道久久a久久精二百| 女生裸体视频一区二区三区| 久久av一区二区三区漫画| 亚洲自拍偷拍福利| 一区二区三区国产在线| 亚洲激情网址| 亚洲电影在线免费观看| 国产在线精品一区二区夜色| 国产精品一页| 国产精品美女| 国产精品久久久久一区二区三区| 欧美精品日韩www.p站| 美女在线一区二区| 久久这里有精品15一区二区三区| 午夜在线精品| 欧美一区精品| 欧美一区免费视频| 久久不见久久见免费视频1| 亚洲欧美制服中文字幕| 亚洲欧美视频在线观看视频| 午夜精品国产精品大乳美女| 亚洲性感美女99在线| 亚洲一区二区黄| 亚洲综合久久久久| 欧美中文在线观看国产| 欧美一区二区三区四区在线观看地址| 亚洲欧美激情视频| 亚洲欧美美女| 久久福利毛片| 欧美插天视频在线播放| 欧美精品亚洲精品| 欧美日韩免费一区二区三区视频| 欧美视频精品一区| 国产精品视频一二| 国产一区二区三区在线免费观看 | 亚洲黄网站在线观看| 日韩亚洲一区二区| 亚洲一区国产视频| 欧美一区二区三区四区在线| 久久久久久久综合| 欧美激情aⅴ一区二区三区| 欧美日韩大片一区二区三区| 国产精品xnxxcom| 国产一区二区三区精品久久久| 亚洲第一精品夜夜躁人人躁| 日韩视频在线播放| 欧美gay视频激情| 欧美日韩一区二区三区在线看 | 欧美大片在线看| 国产精品高精视频免费| 禁断一区二区三区在线| 日韩天天综合| 久久国产精品久久久久久久久久| 免费在线视频一区| 一本色道久久综合狠狠躁篇怎么玩| 欧美一区二区| 欧美精选在线| 国产综合一区二区| 在线视频欧美一区| 久热精品视频| 一区二区三区精品在线| 久久久久久久91| 国产精品一区=区| 亚洲精品久久久久久久久久久久 | 猛干欧美女孩| 亚洲自拍偷拍麻豆| 欧美区国产区| 亚洲欧美资源在线| 欧美电影免费观看高清完整版| 国产欧美日韩中文字幕在线| 亚洲国产精品电影在线观看| 午夜精品国产精品大乳美女| 亚洲精美视频| 久久久综合香蕉尹人综合网| 国产精品拍天天在线| 一区二区欧美视频| 欧美高清在线播放| 久久都是精品| 国产亚洲一本大道中文在线| 亚洲综合色丁香婷婷六月图片|