2012多校联合赛第一场，第十题。

先不考虑可以修复的桥的性质， 则可以将模型简化为n个点的人通过有通过人数上限的有向边，到达一些有人数上限的特殊的边（隧道）。

可以建立最大流模型来求解， 增加一个源点S，和一个汇点T。 S向每个有人的点，连一条容量为人数的边， 图中普通的u->v的有向边，连一条u->v的流量为无穷的边， 桥的流量则为1。 对于隧道，每个隧道可以虚拟出一个点，如u->v的隧道，可以虚拟一个点x，连接u->x,x->v的流量无穷的边， 和x->T的流量为隧道人数上限的边， 求解最大流即可得到最大人数。

现在考虑桥的问题，题目中说明了桥最多只有12座，故可以2^12枚举修复哪些桥，不修复的桥没有花费，连接的边流量为1，要修复的桥则计算花费，边的流量为无穷，这样进行2^12次最大流就可以得到最优解。

 

看了题解后，建图，1Y。

2^12枚举，对桥建边很戏剧，用递归，很好玩。

发现我现在的编程状态很好，200行编下来，基本上想到什么就能编出来什么，网络流，递归，枚举。。以后只要相信自己就好。

相信自己的编码能力！！！

/*Problem : 4309 ( Seikimatsu Occult Tonneru )     Judge Status : AcceptedRunId : 6291376    Language : G++    Author : 2010201211Time : 1687MS Memory : 608K*/#include 
      
       #include 
       
        #include 
        
         using namespace std;#define E 30000#define V 1102#define inf 0xffffstruct Edge{    int u,v,c,next;}edge[E];int n,m,cnt;int cou;int dist[V];int head[V];int que[V];int sta[V];void init(){    cnt=0;    memset(head,-1,sizeof(head));}void addedge(int u,int v,int c){    edge[cnt].u=u;edge[cnt].v=v;edge[cnt].c=c;    edge[cnt].next=head[u];head[u]=cnt++;    edge[cnt].u=v;edge[cnt].v=u;edge[cnt].c=0;    edge[cnt].next=head[v];head[v]=cnt++;}int dinic(int s,int t){    int ans=0;    while(true){        int left,right,u,v;        memset(dist,-1,sizeof(dist));        left=right=0;        que[right++]=s;        dist[s]=0;        while(left
         
          0 && dist[v]==-1){                    dist[v]=dist[u]+1;                    que[right++]=v;                    if(v==t){                        left=right;                        break;                    }                }            }        }        if(dist[t]==-1) break;        int top=0;        int now=s;        while(true){            if(now!=t){                int k;                for(k=head[now];k!=-1;k=edge[k].next){                    if(edge[k].c > 0 && dist[edge[k].u]+1==dist[edge[k].v]) break;                }                if(k!=-1){                    sta[top++]=k;                    now=edge[k].v;                }                else{                    if(top==0) break;                    dist[edge[sta[--top]].v]=-1;                    now=edge[sta[top]].u;                }            }            else{                int flow=inf,ebreak;                for(int i=0;i
          
           edge[sta[i]].c){                        flow=edge[sta[i]].c;                        ebreak=i;                    }                }                ans+=flow;                for(int i=0;i
           
            > n >> m){ for(int i=1;i<=n;i++){ cin >> p[i]; } r=b=t=0; for(int i=1;i<=m;i++){ cin >> a >> bb >> c >> d; if(d<0){ tunnel[t].u=a; tunnel[t].v=bb; tunnel[t++].c=c; } if(d==0){ road[r].u=a; road[r++].v=bb; } if(d>0){ bridge[b].u=a; bridge[b].v=bb; bridge[b++].c=c; } } memset(fb,0,sizeof(fb)); for(int i=0;i<5000;i++){ res[i].cost=0; res[i].num =0; } cou=0; dfs(0); int minc=inf,maxc=-1; for(int i=0;i
            
             maxc){ maxc=res[i].num; } } for(int i=0;i