POJ 1149 最大流+構圖
題意：有m個豬圈，n個商人，每個商人會買固定豬圈的豬，在每個商人買完豬後，我可以調整開著門的豬圈的住的個數，可以從其他開著門的豬圈調過來，問n個商人最多能買走多少豬
思路：o(︶︿︶)o 唉，做最大流的構圖題，做一個就像之前從沒做過最大流似的，膜拜神犇們~~~~，看了後確實簡單，如果這個豬圈是第一次打開，那麼這個豬圈就可以將所有都指向這個商人，就建一條到這個商人的一條這個豬圈的豬的數量，如果不是第一次，那麼就找到上一次打開這個豬圈的人，那個人連一條inf的邊到目前這個商人，想想確實對，之後可以調整的話，不如全都給第一個人，他留下自己的，然後賣給之後來的人，好機智.....神犇們為什麼這麼利害，讓弱雞情何以堪啊........
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1010;
struct edge{
int to,cap,rev;
edge(){}
edge(int a,int b,int c){to=a;cap=b;rev=c;}
};
vector G[maxn];
int level[maxn],iter[maxn];
void add_edge(int from,int to,int cap){
G[from].push_back(edge(to,cap,G[to].size()));
G[to].push_back(edge(from,0,G[from].size()-1));
}
void bfs(int s){
memset(level,-1,sizeof(level));
queueque;
level[s]=0;que.push(s);
while(!que.empty()){
int v=que.front();que.pop();
for(unsigned int i=0;i0&&level[e.to]<0){
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f){
if(v==t) return f;
for(int &i=iter[v];i0&&level[v]0){
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
int max_flow(int s,int t){
int flow=0;
while(1){
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,inf))>0) flow+=f;
}
}
int vis[2010],num[2010];
int main(){
int n,m,a,b,c;
while(scanf("%d%d",&n,&m)!=-1){
for(int i=0;i
