博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
<<<<<<<<<用来存代码哒!!!!>>>>>>>>>>>>
阅读量:7274 次
发布时间:2019-06-29

本文共 1829 字,大约阅读时间需要 6 分钟。

 

#include<iostream> #include<cstring> #include<cstdio> #define MAXN 815 #define INF 1e8 #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) using namespace std; struct edge {     int u,v,w,next; }E[200000]; int head[MAXN],ecnt; int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN]; int l,r,mid; int N,M,scr,sink,vn,num; int k,c1,m; void Insert(int u,int v,int w) {     E[ecnt].u=u;     E[ecnt].v=v;     E[ecnt].w=w;     E[ecnt].next=head[u];     head[u]=ecnt++;     E[ecnt].u=v;     E[ecnt].v=u;     E[ecnt].w=0;     E[ecnt].next=head[v];     head[v]=ecnt++; } int Sap(int s,int t,int n)//核心代码(模版) {     int ans=0,aug=INF;//aug表示增广路的流量     int i,v,u=pre[s]=s;     for(i=0;i<=n;i++)     {         cur[i]=head[i];         dis[i]=gap[i]=0;     }     gap[s]=n;     bool flag;     while(dis[s]<n)     {         flag=false;         for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定义成int &j,why         {             v=E[j].v;             if(E[j].w>0&&dis[u]==dis[v]+1)             {                 flag=true;//找到容许边                 aug=min(aug,E[j].w);                 pre[v]=u;                 u=v;                 if(u==t)                 {                     ans+=aug;                     while(u!=s)                     {                         u=pre[u];                         E[cur[u]].w-=aug;                         E[cur[u]^1].w+=aug;//注意                     }                     aug=INF;                 }                 break;//找到一条就退出             }         }         if(flag) continue;         int mindis=n;         for(i=head[u];i!=-1;i=E[i].next)         {             v=E[i].v;             if(E[i].w>0&&dis[v]<mindis)             {                 mindis=dis[v];                 cur[u]=i;             }         }         if((--gap[dis[u]])==0) break;         gap[dis[u]=mindis+1]++;         u=pre[u];     }     return ans; } int n,f,d; int main() {    while(scanf("%d%d%d",&n,&f,&d)!=EOF)    {        memset(head,-1,sizeof(head));ecnt=0;        scr=0;sink=f+d+n+1;vn=sink+1;        for(int i=1;i<=f;i++)//食物        {            int v;            scanf("%d",&v);            Insert(scr,i,v);        }        for(int i=1+f;i<=d+f;i++) //饮料        {            int v;            scanf("%d",&v);            Insert(i,sink,v);

       }        char t[220];        for(int i=1;i<=n;i++)        //食物        {             scanf("%s",t);             for(int j=0;j<strlen(t);j++)             {                 if(t[j]=='Y')                 Insert(j+1,i+f+d,1);             }        }        for(int i=1;i<=n;i++)        //饮料        {            scanf("%s",t);             for(int j=0;j<strlen(t);j++)             {                 if(t[j]=='Y')                 Insert(i+f+d,j+1+f,1);             }        }     printf("%d",Sap(scr,sink,vn));    }    return 0; }

转载于:https://www.cnblogs.com/amourjun/archive/2013/05/16/5134156.html

你可能感兴趣的文章
PHP实现多服务器session共享之memcache共享
查看>>
【物联网智能网关-15】WAV播放器(WinForm+WavPlay库实例)
查看>>
(转)当别人努力的时候,你在做什么?
查看>>
Go项目结构和模块导入
查看>>
[JSP]JSP 简介
查看>>
android122 zhihuibeijing 主页面搭建
查看>>
在项目开发总的一些感受,希望大家共同来探讨项目管理中的一些看法
查看>>
NeHe OpenGL教程 第四十三课:FreeType库
查看>>
让您知道您的方法是被何“人”调用
查看>>
vue Render scopedSlots
查看>>
Data Mining and Machine Learning in Cybersecurity PDF
查看>>
【英语天天读】First Inaugural Address
查看>>
ASP.NET企业开发框架IsLine FrameWork系列之三--七种武器
查看>>
css3实践—创建3D立方体
查看>>
SQL Server里的INTERSECT
查看>>
在Win7上安装MySql5.2遇到Write configuration file的解决
查看>>
nodejs事件轮询详述
查看>>
抽象类中定义静态方法
查看>>
如何检查DirectX的版本(用于Windows Phone Developer Tools的安装检查)
查看>>
《Linux内核设计与实现》读书笔记(一)-内核简介
查看>>