• 二分的残留题目:
1,Cupid’ puzzle:一个和几何[我最讨厌的类型]相关的题目,带权二分图
要提下线段的处理:可以用三维方阵来处理,然后分别判断x,y的关系,也可以用距离处理,但距离处理有精度丢失.
代码实现如下:
#include <iostream>
#include <fstream>
#include <math.h>
#include <string>
#include <map>
using namespace std;
const int MAXN=30, MAX2N=60, MAXE=900;
typedef struct Edge{
    int i, j, next, w;
}Edge;
typedef struct Point{
    int x, y;
}Point;
Edge es[MAXE];
Point ps[MAX2N];
int first[MAXN], link[MAXN], lx[MAXN], rx[MAXN], wt[MAXN][MAXN]={0}, dis[MAXN][MAXN]={0};
bool l[MAXN], r[MAXN];
int k, n, eid=0; char na[MAXN];
//declaration
void addEdge(int ix, int iy, int w);
inline char* toUpper(char* str);
void KM();
bool find(int v);
void adjust();
//implementation
void addEdge(int ix, int iy, int w){
    es[eid].i=ix, es[eid].j=iy, es[eid].w=w;
    es[eid].next=first[ix], first[ix]=eid; eid++;
}
inline char* toUpper(char* str){
    int slen=strlen(str);
    char* pstr=str;
    for(int i=0; i<slen; i++) str[i]&=0xdf;
    return pstr;
}
void KM(){
    //for lx, and rx vertex point
    memset((void*)lx, 0, sizeof(lx)), memset((void*)rx, 0, sizeof(rx));
    memset((void*)link, 0xff, sizeof(link));
    for(int i=0; i<n; i++){
        int maxx=INT_MIN;
        for(int eid=first[i]; eid!=-1; eid=es[eid].next){
            if(es[eid].w>maxx) maxx=es[eid].w;
        }
        lx[i]=maxx;
    }
    for(int i=0; i<n; i++){
        memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
        while(!find(i)){
            adjust();
            memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
        }
    }
}
bool find(int v){
    l[v]=true;
    for(int eid=first[v]; eid!=-1; eid=es[eid].next){
        if(!r[es[eid].j]&&lx[v]+rx[es[eid].j]==es[eid].w){
            r[es[eid].j]=true;
            if(link[es[eid].j]==-1||find(link[es[eid].j])){
                link[es[eid].j]=v; return true;
            }
        }
    }
    return false;
}
void adjust(){
    int minx=INT_MAX;
    for(int i=0; i<n; i++){
        if(l[i]){
            for(int eid=first[i]; eid!=-1; eid=es[eid].next){
                if(!r[es[eid].j]) minx=min(minx, lx[i]+rx[es[eid].j]-es[eid].w);
            }
        }
    }
    for(int i=0; i<n; i++){
        if(l[i]) lx[i]=lx[i]-minx;
        if(r[i]) rx[i]=rx[i]+minx;
    }
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("cupid.in8");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    map<string, int> dic;
    int px, py; bool exist;
    cin>>k>>n;
    for(int i=0; i<(n<<1); i++){
        memset((void*)na, 0, sizeof(na));
        cin>>ps[i].x>>ps[i].y>>na;
        dic[toUpper(na)]=i;
    }
    for(int i=0; i<n; i++){//O(n^2)
        for(int j=n; j<(n<<1); j++)
            dis[i][j]=dis[j][i]=(ps[i].x-ps[j].x)*(ps[i].x-ps[j].x)+(ps[i].y-ps[j].y)*(ps[i].y-ps[j].y);
    }
    memset((void*)first, 0xff, sizeof(first)), eid=0;//clr for graph
    memset((void*)wt, 0, sizeof(wt));
    memset((void*)na, 0, sizeof(na));
    cin>>na;
    do{
        px=dic[toUpper(na)];
        memset((void*)na, 0, sizeof(na));
        cin>>na; py=dic[toUpper(na)];
        cin>>wt[px][py]; wt[py][px]=wt[px][py];
        memset((void*)na, 0, sizeof(na));
        cin>>na;
    }while(strcmp(toUpper(na), "END")!=0);
    //KM algorithm to get sum of w
    int value;
    for(int i=0; i<n; i++){
        for(int j=n; j<2*n; j++){//i->j
            if(dis[i][j]<=k*k){//less than k
                exist=false;
    for(int p=0; p<2*n; p++){
        if(i!=p&&j!=p){
                        value=ps[i].x*ps[j].y+ps[j].x*ps[p].y+ps[p].x*ps[i].y-ps[p].x*ps[j].y-ps[i].x*ps[p].y-ps[j].x*ps[i].y;
                        if(value==0){
                            if(ps[i].y!=ps[j].y){
                                if(ps[p].y>ps[i].y&&ps[p].y<ps[j].y) exist=true;
                                else if(ps[p].y<ps[i].y&&ps[p].y>ps[j].y) exist=true;
                            }
                            else{
                                if(ps[p].x>ps[i].x&&ps[p].x<ps[j].x) exist=true;
                                else if(ps[p].x<ps[i].x&&ps[p].x>ps[j].x) exist=true;
                            }
                        }
        }
                }//for
                if(!exist) addEdge(i, j-n, wt[i][j]==0?1:wt[i][j]);
            }
        }
    }
    KM();
    int tw=0;
    for(int i=0; i<n; i++){
        if(link[i]!=-1){
            for(int eid=first[link[i]]; eid!=-1; eid=es[eid].next){
                if(es[eid].j==i) tw+=es[eid].w;
            }
        }
    }
    cout<<tw<<endl;
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
2,1325 Machine Schedule,最小覆盖问题,HK做掉的[其实简单的匈牙利就行,出来的结果也比较在情理中,结构多了,反而没有dfs的快]
只是ACM的有些题目确实让人觉得很郁闷,输入描述的莫名其妙.

Source Code

Problem: 1325 User: orlando22
Memory: 300K Time: 32MS
Language: C++ Result: Accepted

Source Code

#include <iostream>

//pku 1325, zju 1364 machine schedule
using namespace std;
const int MAXN=101, MAXE=10001;
typedef struct Edge{
    int i, j, next;
}Edge;
Edge es[MAXE];
int eid=0, firstX[MAXN], linkX[MAXN], linkY[MAXN], distX[MAXN], distY[MAXN], nX, nY, k;
int queue[MAXN*2];

//declaration
bool HK_dfs(int u);
bool HK_bfs();
void addEdge(int i, int j);

//implementation
void addEdge(int i, int j){
    es[eid].i=i, es[eid].j=j;
    es[eid].next=firstX[i], firstX[i]=eid; eid++;
}

//HK algorithgm
bool HK_bfs(){
    bool found=false;
    int top=0, size=0;
    for(int i=0; i<nX; i++){
        if(linkX[i]==-1) queue[size++]=i;
        distX[i]=0;
    }
    memset((void*)distY, 0, sizeof(distY));
    for(;top<size;top++){
        int v=queue[top];
        for(int eid=firstX[v]; eid!=-1; eid=es[eid].next){
            if(!distY[es[eid].j]){
                distY[es[eid].j]=distX[v]+1;
                if(linkY[es[eid].j]==-1) found=true;
                else distX[linkY[es[eid].j]]=distY[es[eid].j]+1, queue[size++]=linkY[es[eid].j];
            }
        }
    }
    return found;
}
bool HK_dfs(int v){
    for(int eid=firstX[v]; eid!=-1; eid=es[eid].next){
        if(distY[es[eid].j]==distX[v]+1){
            distY[es[eid].j]=0;
            if(linkY[es[eid].j]==-1||HK_dfs(linkY[es[eid].j])){
                linkY[es[eid].j]=v, linkX[v]=es[eid].j; return true;
            }
        }
    }
    return false;
}

int main()
{
    //implementation
    int x, y, c;
    while(cin>>nX&&nX){
	cin>>nY>>k;
        memset((void*)firstX, 0xff, sizeof(firstX)),
        memset((void*)linkX, 0xff, sizeof(linkX)),
        memset((void*)linkY, 0xff, sizeof(linkY)), eid=0;
        for(int i=0; i<k; i++){
            cin>>c>>x>>y;
            if(x!=0&&y!=0) addEdge(x, y);
        }
        int res(0);
        while(HK_bfs()){
            for(int i=0; i<nX; i++){
                if(linkX[i]==-1&&HK_dfs(i)) res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

3,UVA 10276 [ZJU 1239] — Hanoi Tower Troubles Again! :还是二分,模型明显,潜在的终止条件有点隐晦:当剩余的无匹配项大于m的柱子数时,可以终止循环。记录其中k[匹配数]+m[柱子数]=n[球数]的最大合理数即可。建图可以使用递归的办法,把当前的n数加到前面的i,并且能使得n+i为完全平方数。注意:二分的MAXNUM大概是m的平方估算既可

下面是二分的代码实现:但50的时候还是超时,所以可以用公式直接过,当然这是题目的特殊性造成的,二分建图才是关键所在
#include <iostream>
#include <math.h>
//uva 10276, zju 1239
using namespace std;
const int MAXN=51, MAXE=2000000, MAXNUM=1400;//搞到1点过,结果发现是MAXNUM开小了
typedef struct Edge{
 int i, j, next;
}Edge;
Edge es[MAXE];
int eid=0, firstX[MAXNUM], linkX[MAXNUM], linkY[MAXNUM], n, m, distX[MAXNUM], distY[MAXNUM], queue[MAXNUM];
//declaration
void clr();
void addEdge(int i, int j);
int HK_Match();
bool HK_bfs();
bool HK_dfs(int v);
//implementation
void clr(){
 eid=0, memset((void*)firstX, 0xff, sizeof(firstX));
}
void addEdge(int i, int j){
 es[eid].i=i, es[eid].j=j;
 es[eid].next=firstX[i], firstX[i]=eid; eid++;
}
int HK_Match(){
 memset((void*)linkX, 0xff, sizeof(linkX)),memset((void*)linkY, 0xff, sizeof(linkY));
 int res(0);
 while(HK_bfs()){
  for(int i=1; i<=n; i++){
   if(linkX[i]==-1&&HK_dfs(i)) res++;
  }
 }
 return res;
}
bool HK_bfs(){
 int top=0, size=0; bool found=false;
 for(int i=1; i<=n; i++){
  if(linkX[i]==-1) queue[size++]=i;
  distX[i]=0;
 }
 memset((void*)distY, 0, sizeof(distY));
 for(;top<size;top++){
  int u=queue[top];
  for(int ed=firstX[u]; ed!=-1; ed=es[ed].next){
   if(!distY[es[ed].j]){
    distY[es[ed].j]=distX[u]+1;
    if(linkY[es[ed].j]==-1) found=true;
    else distX[linkY[es[ed].j]]=distY[es[ed].j]+1, queue[size++]=linkY[es[ed].j];
   }
  }
 }
 return found;
}
bool HK_dfs(int v){
 for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
  if(distY[es[ed].j]==distX[v]+1){
   distY[es[ed].j]=0;
   if(linkY[es[ed].j]==-1||HK_dfs(linkY[es[ed].j])){
    linkX[v]=es[ed].j, linkY[es[ed].j]=v;
    return true;
   }
  }
 }
 return false;
}
int main()
{
 //implementation
 int ncase, value, preV=0, num=0;
 cin>>ncase;
 while(ncase–){
  cin>>m; preV=0;
  clr();
  for(n=1;;n++){//n->1
   num=0;
   for(int i=1; i<n; i++){
    value=sqrt((double)(n+i));
    if(value*value==n+i){
     addEdge(i, n);
    }
   }
   //to find maxMatch
   value=HK_Match();
   for(int i=1; i<=n; i++){
    if(linkX[i]==-1) num++;
   }
   if(n>m&&num>m) break;
   if(value+m==n) preV=n;
  }
  cout<<preV<<endl;
 }
 return 0;
}
公式的实现代码略去,f(n)=floor(n^2/2+n/2-1/2);
 
4,IPSC 2001 — Magic:题目分析倒是很清楚,写的代码要注意流程处理:
  • DFS的年历回溯,生成C(n, (n+1)/2)的所有组合,然后用一个小的回溯来生成C(n, (n-1)/2)的组合。这里用了一个map来处理看对边是否已经存在,写代码的时候没经过大脑,结果map存在选项的时候直接把yid修改了,还好这是唯一的bugs.相当不应该就是了。
  • 匹配可以迅速搞定,但假设严格按照匹配的原始定义,我就还需要做一个C(n, (n-1)/2)和C(n, (n+1)/2)的比较,n^2.所以在添边的时候把去掉的点放在结构体,然后再匹配中用一个辅助结构来处理匹配边对应的去掉点边的eid索引,然后可以在n内可以搞定了。
  • 困惑:map的时候我是用了一个qsort来保证生成int key的唯一性的,在17的上限条件下,程序还是可以的,有更好的办法么?哪位感兴趣,可以给我提点好的建议哈!先谢!
  • 一点思考:如何用构造法来做呢?数学太差,惭愧中![改天再想]
下面是完整的程序[IPSC上的思路,上面有构造法的解答]代码太长了,要反思,尤其是DFS判断逻辑的时候。看数据的上限大概是15,弱了!
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
//IPSC 2001 Magic, max of N is 17.
using namespace std;
const int MAXN=7000, MAXE=49000000, MAXNUM=17;
typedef struct Edge{
    int i, j, mid, next;
}Edge;
Edge es[MAXE];
vector<int> X[MAXN], Y[MAXN];//clear for each time.
map<int, int> toES;//for all
int eid=0, xid=0, yid=0, n, k, num, firstX[MAXN], distX[MAXN], distY[MAXN], linkX[MAXN], linkY[MAXN], queue[MAXN];
int linkXE[MAXN], linkYE[MAXN];
int lis[MAXNUM], order[MAXNUM];
//declaration
int inline Combine(int n, int m);
void dfs(int d);//d->0…k-1, k to collect data.
void clr();
void addEdge(int i, int j, int mid);
int HK();
bool HK_bfs();
bool HK_dfs(int v);
int cmp(const void* p1, const void* p2);
//implementation
int inline Combine(int n, int m){
    assert(n>=m&&n>0&&m>=0);
    if(m==0) return 1;
    return n/m*Combine(n-1, m-1);
}
void clr(){
    eid=0, xid=0, yid=0;
    memset((void*)firstX, 0xff, sizeof(firstX));
    for(int i=0; i<n; i++) lis[i]=i+1;
    for(int i=0; i<MAXN; i++) X[i].clear(), Y[i].clear();
    toES.clear();
}
void dfs(int d){//d==k terminate.
    if(d==num){//get out of X, Y vector
        for(int i=0; i<num; i++) X[xid].push_back(lis[i]);
        for(int i=0, key=0, pyid=-1; i<num; i++){//swap lis[k-1] with lis[i]
            key=0;
            if(i!=num-1) lis[i]^=lis[num-1], lis[num-1]^=lis[i], lis[i]^=lis[num-1];
            memcpy((void*)order, (void*)lis, sizeof(int)*(num-1));
            qsort((void*)order, num-1, sizeof(int), cmp);//dummy implementation for hashtable
            for(int j=0; j<num-1; j++) key+=key*10+order[j];
            if(toES.find(key)!=toES.end()){//here : yid can’t be modify, if no-entry has been inserted.
                pyid=toES[key], addEdge(xid, pyid, lis[num-1]);
            }
            else{
                toES[key]=yid;//find the toES[key]’s es id.
                for(int j=0; j<num-1; j++) Y[yid].push_back(order[j]);
                addEdge(xid, yid, lis[num-1]), yid++;
            }
            //keep eid as mid in inneral logic of addEdge.
            if(i!=num-1) lis[i]^=lis[num-1], lis[num-1]^=lis[i], lis[i]^=lis[num-1];
        }
        xid++;//increase xid..
        return;
    }
    for(int i=d; i<n; i++){
        if(d==0||lis[d-1]<lis[i]){//lis[0…n-1] has no-duplicate elements
            if(d!=i) lis[d]^=lis[i], lis[i]^=lis[d], lis[d]^=lis[i];
            dfs(d+1);
            if(d!=i) lis[d]^=lis[i], lis[i]^=lis[d], lis[d]^=lis[i];
        }
    }
}
int cmp(const void* p1, const void* p2){//p1 in the back
    return *((int*)p1)>*((int*)p2);
}
void addEdge(int i, int j, int mid){
    es[eid].i=i, es[eid].j=j, es[eid].mid=mid;//missing number
    es[eid].next=firstX[i], firstX[i]=eid; eid++;
}
int HK(){
    memset((void*)linkX, 0xff, sizeof(linkX)), memset((void*)linkY, 0xff, sizeof(linkY));//xid
    int res(0);
    while(HK_bfs()){
        for(int i=0; i<xid; i++)
            if(linkX[i]==-1&&HK_dfs(i)) res++;
    }
    return res;
}
bool HK_bfs(){
    int top=0, size=0;
    for(int i=0; i<xid; i++){
        if(linkX[i]==-1) queue[size++]=i;
        distX[i]=0;
    }
    memset((void*)distY, 0, sizeof(distY));
    bool found=false;
    for(;top<size;top++){
        int v=queue[top];
        for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
            if(!distY[es[ed].j]){
                distY[es[ed].j]=distX[v]+1;
                if(linkY[es[ed].j]==-1) found=true;
                else distX[linkY[es[ed].j]]=distY[es[ed].j]+1, queue[size++]=linkY[es[ed].j];
            }
        }
    }
    return found;
}
bool HK_dfs(int v){
    for(int ed=firstX[v]; ed!=-1; ed=es[ed].next){
        if(distY[es[ed].j]==distX[v]+1){
            distY[es[ed].j]=0;
            if(linkY[es[ed].j]==-1||HK_dfs(linkY[es[ed].j])){//modify logic here!
                linkX[v]=es[ed].j, linkY[es[ed].j]=v;//standard
                linkXE[v]=ed, linkYE[es[ed].j]=ed;
                return true;
            }
        }
    }
    return false;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int ncase;
    cin>>ncase;
    while(ncase–){
        cin>>n;
        if(!(n&0x1)){cout<<-1<<endl; continue;}
        num=(n+1)/2, k=Combine(n, num);//n is odd judgement
        clr(),dfs(0);//construct graph
        int res=HK();
        assert(res==xid&&xid==yid);//perfect match assertion
        //for output
        for(int i=0; i<xid/*yid*/; i++){
            assert(linkY[i]!=-1);
            for(vector<int>::iterator p=Y[i].begin(); p!=Y[i].end(); p++){
                cout<<(*p)<<" ";//PE error
            }
            cout<<"-> ";
            cout<<es[linkYE[i]].mid<<endl;
        }
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
 
  •  最大流的残留题目:一道让人看着比较茫然的题目,黑书描述的更让人茫然。[解后的感觉是又是一个多维变量,枚举转化的思路]

想了下,T作为变参来枚举状态即可。把每个太空站在T时刻的状态作为图结点,进而将太空船的转移作为边;由于可以留在太空站上,所以从(i,T-1)->(i,T)也是一个状态转化边。剩下就是Dicnic算法求解。题目描述和代码实现附上。

家  园

由于人类对自然的疯狂破坏,人们意识到在大约2300年之后,地球不能再居住了,于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,2177年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。
现有n个太空站处于地球与月球之间(编号1..n),m艘公共交通太空船在其中来回穿梭,每个太空站Si可容纳无限的人,每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi,将周期性地停靠一系列的太空站(Si1,Si2…Sir),如:(1,3,4)表示停靠太空站1 3 4 1 3 4 1 3 4 …。 任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站(或地球、月球)时上船或下船。初始时的人全在地球上,太空船全在初始站(太空船pi处于Si1),目标是让所有的人尽快地全部转移到月球上。
输入:
文件第一行为三个正整数 n(太空站个数)、 m(太空船个数)、 k(需要运送的地球上的人的个数),其中 1<=m<=13, 1<=n<=20, 1<=k<=50。
接下来的n行给出了太空船的信息,第i+1行说明太空船pi,此行第一个数表示pi可容纳的人数Hpi,第二个数表示pi停靠一个周期的太空站个数r,1<=r<=n+2, 随后r个数便是停靠的太空站的编号(Si1,Si2,…,Sir), 地球用0表示,月球用-1表示。0时刻时,所有太空船都在初始站,随后开始运行,在时刻1,2,3…等正点时刻各艘太空船停靠相应的太空站,即人只有在0,1,2…等正点时刻才能上下太空船。
输出:
    文件只有一个数,若问题有解,输出完成全部人员安全转移的时刻,否则输出0。
输入输出示例:      
输入文件:2 2 1  //m=2, n=2                         
          1 3 0 1 2
          1 3 1 2 –1
输出文件:5

代码实现:Dicnic有点忘记了,唉!
// Homeland.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <assert.h>
#include <stdlib.h>
//CTSC 1999 homeland
using namespace std;
const int MAXT=1000, MAXSN=21000, MAXSE=42000, MAXM=13;
//mapping (i, t)->mt+i
typedef struct Edge{
    int i, j, next, op, f, c;
}Edge;
Edge es[MAXSE];
int m, n, k, first[MAXSN], eid=0, pre[MAXSN], firstc[MAXSN], queue[MAXSN], ptr[MAXSN], cur[MAXM], cap[MAXM];
vector<int> ship[MAXM];
bool visited[MAXSN];
//declaration
void clr();
void addEdge(int start, int end, int cap);
//implementation
void clr(){
    eid=0, memset((void*)first, 0xff, sizeof(first));
    memset((void*)cur, 0, sizeof(cur));//start 0
}
void addEdge(int start, int end, int cap){
    assert(eid<MAXSE);
    if(!cap) return;
    es[eid].i=start, es[eid].j=end, es[eid].f=0, es[eid].c=cap;
    es[eid].next=first[start], first[start]=eid, es[eid].op=eid+1; eid++;
    es[eid].i=end, es[eid].j=start, es[eid].f=0, es[eid].c=-1;
    es[eid].next=first[end], first[end]=eid, es[eid].op=eid-1; eid++;
}
//maxflow algorithm
int Dicnic(int sv, int st);
void bfslevel(int sv, int st);
void dfsflow(int sv, int st);
//implementation
int Dicnic(int sv, int st){
    int maxflow=0;
    while(true){
        bfslevel(sv, st);
        if(pre[st]==INT_MAX) break;
        dfsflow(sv, st);
    }
    for(int ed=first[sv]; ed!=-1; ed=es[ed].next){
        if(es[ed].c>0) maxflow+=es[ed].f;
    }
    return maxflow;
}
void bfslevel(int sv, int st){
    assert(sv<st);
    for(int i=sv; i<=st; i++) pre[i]=INT_MAX;
    int top=0, size=0;
    pre[sv]=sv, queue[size++]=sv;
    for(;top<size;top++){
        int v=queue[top];
  if(v==st) return;
        for(int ed=first[v]; ed!=-1; ed=es[ed].next){
            if(pre[es[ed].j]>pre[v]+1){//in the residental graph
                if(es[ed].c>es[ed].f||(es[ed].c==-1&&es[ed].f>0)){
                    queue[size++]=es[ed].j, pre[es[ed].j]=pre[v]+1;
                }
            }
        }
    }
}
void dfsflow(int sv, int st){
    memset((void*)ptr, 0, sizeof(ptr)), memset((void*)visited, 0, sizeof(visited));
    memcpy((void*)firstc, (void*)first, sizeof(first));
    int top=0; queue[top]=sv;
    while(top>-1){
        if(queue[top]==st){
            int fmin=INT_MAX, tj=-1, value;
            for(int j=top; j>0; j–){
                if(es[ptr[queue[j]]].c>es[ptr[queue[j]]].f){
                    if((value=es[ptr[queue[j]]].c-es[ptr[queue[j]]].f)<fmin) fmin=value;
                }
                if(es[ptr[queue[j]]].c==-1&&es[ptr[queue[j]]].f>0){
                    if((value=es[ptr[queue[j]]].f)<fmin) fmin=value;
                }
            }
            //update
            for(int j=top; j>0; j–){
                if(es[ptr[queue[j]]].c>es[ptr[queue[j]]].f){
                    es[ptr[queue[j]]].f+=fmin, es[es[ptr[queue[j]]].op].f+=fmin;
                    if(es[ptr[queue[j]]].f==es[ptr[queue[j]]].c) tj=j;
                }
                if(es[ptr[queue[j]]].c==-1&&es[ptr[queue[j]]].f>0){
                    es[ptr[queue[j]]].f-=fmin, es[es[ptr[queue[j]]].op].f-=fmin;
                    if(es[ptr[queue[j]]].f==0) tj=j;
                }
            }
            if(tj!=-1)top=tj-1;
        }
        else{
            int tmp=firstc[queue[top]], tp=queue[top];
            for(;tmp!=-1;tmp=es[tmp].next){
                if(!visited[es[tmp].j]&&pre[es[tmp].j]==pre[tp]+1){
                    if(es[tmp].c>es[tmp].f||(es[tmp].c==-1&&es[tmp].f>0)){
                        firstc[tp]=es[tmp].next;
                        queue[++top]=es[tmp].j, ptr[queue[top]]=tmp;//found one trip to st
                        break;
                    }
                }
            }
            if(tmp==-1){visited[tp]=true;top–;}
        }
    }
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("9.in");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int num, l, t=0, maxflow=0, pre_loc, cur_locs, tn;
    cin>>n>>m>>k;
 tn=n+2;
    for(int i=0; i<m; i++){
        cin>>cap[i]>>num;
        for(int j=0; j<num; j++){
            cin>>l;
            if(l==-1) l=n+1;
            ship[i].push_back(l);//for location check
        }
    }
    clr();
    do{
        t++;
        for(int i=0; i<m; i++){//其实只有这一段,其他都是模型求解。
            pre_loc=ship[i][cur[i]], cur_locs=ship[i][(cur[i]+1)%ship[i].size()];
            addEdge(pre_loc+tn*(t-1), cur_locs+tn*t, cap[i]);
            //modify cur[i]
            cur[i]=(cur[i]+1)%ship[i].size();
        }
  for(int i=0; i<n+3; i++)
   addEdge(i+tn*(t-1), i+tn*t, INT_MAX);
        maxflow+=Dicnic(0, n+1+tn*t);
    }while(maxflow<k&&t<MAXT);
    if(t<MAXT) cout<<t<<endl;
    else cout<<0<<endl;
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase

Advertisements