P1231 教辅的组成

https://www.luogu.org/problemnew/show/P1231

这道题不难发现是网络流题，主要要想到怎么建图，然后跑遍网络流就ok了

我们先对练习册和书连一条边容量为1，然后书与答案连一条边容量为1，但是这样有问题，因为书的流量可能会很多，所以我们要把书拆成两堆，然后书一与书二之间连一条边容量为一，然后我们建一个超级源点，超级汇点，连起来，容量都是一，这样建图就好了，然后dinic跑一次，就ok

附上代码

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define ll long long 9 using namespace std; 10 #define INF 0x3f3f3f 11 struct node 12 { 13 int from,to,cap,flow; 14 }; 15 vector
             
              edges; 16 vector
              
               load[1000005]; 17 int n,m,s,t; 18 int cur[1000005]; 19 int d[1000005]; 20 void add(int u,int v,int w) 21 { 22 edges.push_back((node){u,v,w,0}); 23 edges.push_back((node){v,u,0,0}); 24 int x=edges.size(); 25 load[u].push_back(x-2); 26 load[v].push_back(x-1); 27 } 28 bool bfs() 29 { 30 memset(d,0,sizeof(d)); 31 queue
               
                q; 32 q.push(s); 33 d[s]=1; 34 while(!q.empty()) 35 { 36 int u=q.front();q.pop(); 37 int x=load[u].size(); 38 for(int i=0;i
                
                 v.flow) 42 { 43 d[v.to]=d[u]+1; 44 q.push(v.to); 45 } 46 } 47 } 48 return d[t]!=0?1:0; 49 } 50 int dfs(int u,int mini) 51 { 52 if(mini==0||u==t) 53 return mini; 54 int x=load[u].size(); 55 int flow=0; 56 for(int &i=cur[u];i
                 
                  0) 61 { 62 v.flow+=f; 63 edges[load[u][i]^1].flow-=f; 64 flow+=f; 65 mini-=f; 66 if(mini==0)break; 67 } 68 } 69 return flow; 70 } 71 void dinic() 72 { 73 int ans=0; 74 while(bfs()) 75 { 76 memset(cur,0,sizeof(cur)); 77 ans+=dfs(s,INF); 78 } 79 printf("%d",ans); 80 } 81 int n1,n2,n3,m1,m2,m3; 82 int main() 83 { 84 s=0; 85 scanf("%d %d %d",&n1,&n2,&n3); 86 scanf("%d",&m1); 87 for(int i=1;i<=m1;i++) 88 { 89 int x,y; 90 scanf("%d %d",&x,&y); 91 add(y,x+n2,1); 92 } 93 scanf("%d",&m2); 94 for(int i=1;i<=m2;i++) 95 { 96 int x,y; 97 scanf("%d %d",&x,&y); 98 add(x+n2+n1,2*n1+n2+y,1); 99 }100 for(int i=1;i<=n2;i++)101 {102 add(0,i,1);103 }104 for(int i=1;i<=n1;i++)105 {106 add(n2+i,n2+n1+i,1);107 }108 int end=n1+n2*2+n3+1;109 t=end;110 for(int i=1;i<=n1;i++)111 {112 add(n2+2*n1+i,end,1);113 }114 dinic();115 }
                 
                
               
              
             
            
           
          
         
        
       
      

 

P3324 [SDOI2015]星际战争

https://www.luogu.org/problemnew/show/P3324

这道题只要想到怎么建图，然后二分枚举时间，就ok了，一定要考虑精度问题！！

首先建立一个超级源点S和超级汇点T，将每个机器人跟汇点相连，容量为机器人的护甲值，然后激光器跟机器人相连，容量为INF（极大的数），

最后用二分的时间time*b[i](b[i]第i个激光每秒的伤害）的值当作容量将源点与第i个激光器相连，跑遍dinic，判断是否成立，不成立就接着二分

附上代码

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #define MAXN 60000 11 #define INF 21474873647990000 12 #define LL long long 13 using namespace std; 14 LL S,T,a[MAXN],b[MAXN],c[1001][1001]; 15 LL n,m,cnt,head[MAXN<<1],leve[MAXN<<1]; 16 LL sum; 17 18 inline LL read(){ 19 LL x=0,f=1; char ch=getchar(); 20 for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; 21 for(;isdigit(ch);ch=getchar())x=ch-'0'+(x<<3)+(x<<1); 22 return x*f; 23 } 24 25 struct node{ 26 LL to,next; 27 LL f; 28 }w[MAXN<<2]; 29 30 void add(LL u,LL v,LL fl){ 31 cnt++; 32 w[cnt].to=v;w[cnt].f=fl;w[cnt].next=head[u];head[u]=cnt; 33 cnt++; 34 w[cnt].to=u;w[cnt].f=0; w[cnt].next=head[v];head[v]=cnt; 35 } 36 37 queue
               
                q; 38 39 bool bfs(){ 40 memset(leve,-1,sizeof(leve)); 41 q.push(S); 42 leve[S]=0; 43 while(!q.empty()){ 44 LL ans=q.front(); 45 q.pop(); 46 for(LL i=head[ans];i!=-1;i=w[i].next){ 47 if(leve[w[i].to]==-1 && w[i].f){ 48 leve[w[i].to]=leve[ans]+1; 49 q.push(w[i].to); 50 } 51 } 52 } 53 if(leve[T]==-1)return 0; 54 return 1; 55 } 56 57 58 LL dfs(LL s,LL f){ 59 if(s==T || f==0) return f; 60 LL tmp=0; 61 for(LL i=head[s];i!=-1 && tmp
                
                 >1,ans=dinic(mid);108 if(ans==sum)y=mid-1;109 else x=mid+1;110 }111 printf("%.6f",y/1000.0);112 return 0;113 }
                
               
              
             
            
           
          
         
        
       
      

 

P2774 方格取数问题

https://www.luogu.org/problemnew/show/P2774

相邻的数字只能选一个，联想到二分图，相邻的点分别放在x、y端，他们之间连一条边，为什么他们之间连一条边呢，因为相邻数字的关系有且仅有相邻为影响，我们需要把影响转化到模型上，

不相邻的点建边虽然思考起来更直观，但是边数太多了，反而更难理清思路，要使边有意义且合法，我们需要构造起始点和终点，因为x的每个点地位相同，那么都和s点相连，同理y和t相连

显然对于构造出来的这个图，我们要尝试把题意转化进去，即答案需要的是一种什么图。x和y相连的两个点只能要一个，这是题意，那么结果图中不能有s-u-v-t完整的4条弧构成的“链”，

断链的方法显然为最小割，最小割最大流是很重要的定理。模拟一下最大流的过程，举几个小例子就能明白我们割掉的是小的，留下来的是大的和小的的差那么结果就显而易见了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #define INF 21474836 9 using namespace std;10 11 struct node{12 int to,next,f;13 }w[1000001];14 int sum=-1,num[101][101],mp[101][101],head[100001],p[100001];15 16 void add(int u,int v,int fl){17 sum++;18 w[sum].to=v;w[sum].next=head[u];w[sum].f=fl;head[u]=sum;19 sum++;20 w[sum].to=u;w[sum].next=head[v];w[sum].f=0; head[v]=sum;21 }22 queue
             
              q;23 bool bfs(int s,int t){24 memset(p,-1,sizeof(p));25 q.push(s); p[s]=0;26 while(!q.empty()){27 int ans=q.front(); q.pop();28 for(int i=head[ans];i!=-1;i=w[i].next){29 if(p[w[i].to]==-1 && w[i].f!=0){30 p[w[i].to]=p[ans]+1;31 q.push(w[i].to);32 }33 }34 35 }36 if(p[t]==-1)return 0;37 return 1;38 }39 int dfs(int s,int t,int maxf){40 if(s==t||maxf==0)return maxf;41 int tmp=0;42 for(int i=head[s];i!=-1 && tmp
              
               0) add(num[i][j],num[i-1][j],INF);86 if (j>0) add(num[i][j],num[i][j-1],INF);87 add(s,num[i][j],mp[i][j]);88 }89 else add(num[i][j],t,mp[i][j]);90 }91 }92 int maxflow=dinic(s,t);93 printf("%d\n",ans-maxflow);94 return 0;95 }