POJ – 1149 PIGS (网络流 dinic 建图方法可学习)

图论真的好难啊 这题看了好久终于a掉了

题目思路

按照一般的朴素建图想法就是把客人猪圈之间都建边
用超级源点和超级汇点连接
但是这么建边 边的个数会过大
所以要减少边
有一种很巧妙而建图方法
只将商人看作图上的点
从源点建到每个商人的边 边权为商人能开的猪舍有的猪的个数
因为可能多个商人访问一个猪舍
所以记录访问的先后顺序 在将这些商人建边 边权值为inf
最后对商人和汇点建边 边权值为商人要买的数量
还有可能会有重边 要处理 这题数据好像有点水 没处理也过了。。。。

ac代码

#include <stdio.h>#include <iostream>#include <algorithm>#include <math.h>#include <string.h>#include <vector>#include <stack>#include <queue>#include <map>#include <set>#include <utility>#define pi 3.1415926535898#define ll long long#define lson rt<<1#define rson rt<<1|1#define eps 1e-6#define ms(a,b) memset(a,b,sizeof(a))#define legal(a,b) a&b#define print1 printf(\"111\\n\")using namespace std;const int maxn = 1e6+10;const int inf = 0x3f3f3f3f;const ll llinf =0x3f3f3f3f3f3f3f3f;const int mod = 1e9+7;int n,m,len;int pig[maxn],want[maxn],d[maxn],first[maxn];vector<int>vec[maxn];struct node{int to,next,v;}e[maxn];void add(int u,int v,int w){e[len].to=v;e[len].next=first[u];e[len].v=w;first[u]=len++;e[len].to=u;e[len].next=first[v];e[len].v=0;first[v]=len++;}void getmap(){for(int i=1;i<=m;i++){int a=vec[i][0];add(0,a,pig[i]);//连接源点与商人for(int j=0;j<vec[i].size()-1;j++){int x=vec[i][j];int y=vec[i][j+1];add(x,y,inf);//连接先后访问的商人}}for(int i=1;i<=n;i++)add(i,n+1,want[i]);//连接商人与汇点}bool makelevel(int s,int t)//查询增广路{ms(d,0);queue<int>q;d[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();if(x==t)return true;for(int i=first[x];i!=-1;i=e[i].next){if(d[e[i].to]==0&&e[i].v!=0){q.push(e[i].to);d[e[i].to]=d[x]+1;}}}return false;}int dfs(int x,int flow,int t)//做求最大流的操作{//printf(\"x %d\\n\",x);if(x==t)return flow;int sum=0;for(int i=first[x];i!=-1;i=e[i].next){if(e[i].v!=0&&d[e[i].to]==d[x]+1){int tem=dfs(e[i].to,min(flow-sum,e[i].v),t);e[i].v-=tem;e[i^1].v+=tem;sum+=tem;if(sum==flow)return sum;}}return sum;}int main(){scanf(\"%d%d\",&m,&n);ms(first,-1);for(int i=1;i<=m;i++)scanf(\"%d\",&pig[i]);for(int i=1;i<=n;i++){int x,y;scanf(\"%d\",&x);for(int j=1;j<=x;j++){scanf(\"%d\",&y);vec[y].push_back(i);}scanf(\"%d\",&want[i]);}getmap();//建图int ans=0;while(makelevel(0,n+1)){ans+=dfs(0,inf,n+1);}printf(\"%d\\n\",ans);}