超级大水题
Description
?史努比最愛水題了，他知道現在他要挑戰的是一道超級大水題哦。不過因為太水了，而且他又很懶,所以把這道水題推給了你們。
?
有n個(不包括ZSTU和火車東站)車站介于ZSTU和火車東站之間，一共有m輛公交車往返于這些車站和火車東站。每個車站假設可以站無數個人，每輛車最多承載H[i]個人，經過S[i]個車站。假設一輛車依次經過1,2,3，這三個車站，那么它將一直往復1->2->3->1->2...現在認為車從一個站到下一個站要花費1個小時，人只能在車站或ZSTU,火車東站上下車，初始時有k個人在ZSTU（0站）,所有的車都在初始站（所給車站的第一個車站為初始站)，現在問你們最快讓全部人從ZSTU到火車東站要多少小時。所有車同時運行。
?
Input
?第一行有一個T<=10，表示T組測試樣例，第二行三個數n(車站數目),m(車數目),k(人數)，(n<=13,m<=20,k<=50);接下來的m行給出車信息,每行給出H[i](能承載的最大人數),S[i](經過的車站數目),還有依次給出S[i]個車站編號。ZSTU用0編號表示，火車東站用-1表示。
?
Output
?若無解則輸出-1，否則逐行輸出答案。
?
Sample Input
2 2 2 1 1 3 0 1 2 1 3 1 2 -1 2 3 3 1 2 0 2 1 2 1 2 1 2 1 -1Sample Output
5 7HINT
?
?第一個樣例，一人從0站乘坐1號公交車途徑1站，到2站下車，花費2S；此時2號車位于-1站，再經過2S，2號車從-1站途徑1站到2站，人上2號車再經過1S到達-1站，共花費5S。或者一人從0站乘坐一號公交車到1站下車，花費1S，此時2號車位于2站，再經過2S到1站，人上2號車再經過2S到達-1站，共花費5S。
?
題解：
首先判斷學校到火車東站能不能到站，即是否在同一個集團里面，用并查集就可以了。然后跑網絡流，網絡流跑一次后會更改原來儲存的邊的信息，因此可以枚舉時間進行網絡流，按照時間建邊，在上一個時間段跑網絡流的基礎上，繼續建圖在繼續跑網絡流，將每次的最大流加起來直到總和大于等于k就可以返回當前天數了。
具體操作是將第i-1小時的第j個車的信息向第i小時的第j個車進行連邊，容量為INF，將每輛車第i-1小時所待的公交車站向第i小時所待的公交車站連邊，容量為車的最大載人數。
#include <bits/stdc++.h> //CLOCKS_PER_SEC #define se second #define fi first #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define Pii pair<int,int> #define Pli pair<ll,int> #define ull unsigned long long #define pb push_back #define fio ios::sync_with_stdio(false);cin.tie(0) const double Pi=3.14159265; const int N=1e3+5; const ull base=163; const int INF=0x3f3f3f3f; using namespace std; int n,m,k,s,t; int head[10100],to[100010],cur[10100],nx[100010]; int cap[100010]; int tot=0; void add(int x,int y,int c){to[tot]=y;nx[tot]=head[x];cap[tot]=c;head[x]=tot++;to[tot]=x;nx[tot]=head[y];cap[tot]=0;head[y]=tot++; } void init(int n){tot=0;memset(head,-1,sizeof(head)); } int d[N]; int bfs(){memset(d,-1,sizeof(d));queue<int>q;q.push(s);d[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];~i;i=nx[i]){int v=to[i];if(d[v]==-1&&cap[i]>0){d[v]=d[u]+1;q.push(v);}}}return d[t]!=-1; } int dfs(int s,int a){if(s==t||a==0)return a;int flow=0,f;for(int &i=cur[s];~i;i=nx[i]){int v=to[i];if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){flow+=f;cap[i]-=f;cap[i^1]+=f;a-=f;if(a==0)break;}}return flow; } int dinic(){int ans=0;while(bfs()){for(int i=0;i<=1000;i++)cur[i]=head[i];while(int di=dfs(s,INF)){ans+=di;}}return ans; } int ship[N][N]; int num[N]; int r[N]; int fa[N]; int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]); }bool check(int x,int y){if(F(x)==F(y))return 1;else return 0; } int cal(int a,int d){return d*n+a; } void solve(){int flow=0;int i;init(n);// n -1 n-1 0add(s,cal(n-1,0),INF);add(cal(n,0),t,INF);for(i=1;flow<k;i++){add(s,cal(n-1,i),INF);add(cal(n,i),t,INF);for(int j=1;j<=n;j++){add(cal(j,i-1),cal(j,i),INF);}for(int j=1;j<=m;j++){int a=(i-1)%num[j]+1;int b=i%num[j]+1;add(cal(ship[j][a],i-1),cal(ship[j][b],i),r[j]);}flow+=dinic();}printf("%d\n",i-1); } int main(){// clock_t start, end;int T;scanf("%d",&T);while(T--){s=0,t=1000;scanf("%d%d%d",&n,&m,&k);for(int i=0;i<=n+2;i++)fa[i]=i;for(int i=1;i<=m;i++){scanf("%d%d",&r[i],&num[i]);for(int j=1;j<=num[i];j++){scanf("%d",&ship[i][j]);if(ship[i][j]==0)ship[i][j]=n+1;if(ship[i][j]==-1)ship[i][j]=n+2;if(j>1){fa[F(ship[i][j-1])]=F(ship[i][j]);}}}n+=2;if(check(n, n-1)){solve();}else{printf("0\n");}}// end = clock();// cout << "time :"<<(double)(end - start) / CLOCKS_PER_SEC << endl;return 0; } /**/?
總結
