codeforces gym 100357 J (网络流）

题目大意

　　有n种物品，m种建筑，p个人。 n,m,p∈[1，20]

　　每种建筑需要若干个若干种物品来建造。每个人打算建造一种建筑，拥有一些物品。

　　主角需要通过交易来建造自己的建筑，交易的前提是对方用多余的物品来换取自己需要的物品。

　　询问主角是否能建造成功自己的建筑，并给出方案。　　

解题分析

　　超级恶心的读入，而且有一组数据的给出方式里没有逗号，和样例所示不同= =

　　根据py的性质很容易想到用网络流来做。将每种物品拆成x，y两份。

　　若主角多了a物品b件，连一条S到物品a，x部流量为b的边。

　　若主角少了a物品b件，连一条物品a，y部到T流量为b的边。

　　若某人少了a物品b件，连一条物品a，x部流量为b到该人流量为b的边。

　　若某人多了a物品b件，连一条该人到物品a，y部流量为b到该人流量为b的边。　　模拟了一次交易的进行。

　　再由每个物品的y部向每个物品的x部连一条流量为无穷大的边。　　表示交易可以不停的进行。

　　跑一遍网络流，如果是满流的话，说明可以成功。

　　输出方案则再残量网络上进行一次dfs，将每一次的交易的情况依次输出。

参考程序

 #include <bits/stdc++.h>

 using namespace std;

 #define rep(i,x,y) for (int i=x;i<=y;i++)

 //#define DEBUG

 const int N=;

 const int INF=;

 int n,m,p,sum,lt[N],cur[N],S,TT,T,dis[N];

 struct node{

     int u,v,f,nt;

 }eg[N*];

 map <string,int> build_number;

 map <string,int> res_number;

 string res_name[N];

 string build_name[N];

 string people_name[N];

 string my_build;

 int build_need[N][N];

 int people_has[N][N];

 void add(int u,int v,int f)

 {

     #ifdef DEBUG

     cout<<u<<" "<<v<<" "<<f<<endl;

     #endif

     eg[++sum]=(node){u,v,f,lt[u]}; lt[u]=sum;

     eg[++sum]=(node){v,u,,lt[v]}; lt[v]=sum;

 }

 bool bfs()

 {

     memset(dis,,sizeof(dis));

     queue <int> Q;

     dis[S]=; Q.push(S);

     while (!Q.empty())

     {

         int u=Q.front(); Q.pop();

         for (int i=lt[u];i;i=eg[i].nt)

         {

             int v=eg[i].v;

             if (eg[i].f && !dis[v])

             {

                 dis[v]=dis[u]+;

                 Q.push(v);

             }

         }

     }

     return dis[T];

 }

 int dfs(int u,int flow)

 {

     if (u==T) return flow;

     int res=,f;

     for (int &i=cur[u];i;i=eg[i].nt)

     {

         int v=eg[i].v;

         if (eg[i].f && dis[v]==dis[u]+)

         {

             f=dfs(v,min(flow-res,eg[i].f));

             res+=f;

             eg[i].f-=f; eg[i^].f+=f;

             if (res==flow) break;

         }

     }

     return res;

 }

 int dinic()

 {

     int sum=;

     while (bfs())

     {

         rep(i,S,T) cur[i]=lt[i];

         sum+=dfs(S,INF);

     }

     return sum;

 }

 void solve(int u,int fa)

 {

     //cout<<u<<" "<<fa<<endl;

     if (u==T) return;

     for (int i=lt[u];i;i=eg[i].nt)

         if (i%== && eg[i^].f)

         {

             int v=eg[i].v;

             int times=;

             if (u==S) times=eg[i^].f;

             rep(j,,times)

             {

                 eg[i^].f--;

                 if (u>=n+ && u<=n+p)

                 {

                     //cout<<u-n<<" "<<fa<<" "<<v-n-p<<" "<<v<<endl;

                     cout<<"trade with "<<people_name[u-n]<<" "<<res_name[fa]<<" for "<<res_name[v-n-p]<<endl;

                 }

                 solve(v,u);

             }

             if (u!=S) break;

         }

 }

 int main()

 {

     freopen("trading.in","r",stdin);

     #ifndef DEBUG

     freopen("trading.out","w",stdout);

     #endif

     char ch;

     cin.sync_with_stdio();

     memset(lt,,sizeof(lt)); sum=;

     cin>>p>>n>>m;

     S=,TT=n*+p+,T=n*+p+;

     int total=;

     rep(i,,n)

     {

         cin>>res_name[i];

         res_number[res_name[i]]=i;

     }

     rep(i,,m)

     {

         cin>>build_name[i];

         build_number[build_name[i]]=i;

         string s;

         cin>>s;

         for (;;)

         {

             int x;

             cin>>x>>s;

             if (s[s.length()-]==',')

             {

                 s.erase(s.end()-);

                 build_need[i][res_number[s]]=x;

             }

             else

             {

                 build_need[i][res_number[s]]=x;

             }

             cin.get(ch);

             if (ch=='\n') break;

         }

     }

     string s; cin>>s>>s>>s;

     if (s[s.length()-]==',') s.erase(s.end()-);

     my_build=s;

     cin.get(ch);

     if (ch!='\n')

     {

         string t; cin>>t;

         for (;;)

         {

             int x; cin>>x>>t;

             if (t[t.length()-]==',')

             {

                 t.erase(t.end()-);

                 people_has[][res_number[t]]=x;

             }

             else

             {

                 people_has[][res_number[t]]=x;

             }

             cin.get(ch);

             if (ch=='\n') break;

         }

     }

     rep(i,,n)

     {

         int y=people_has[][i]-build_need[build_number[s]][i];

         if (y>) add(S,i,y);

         if (y<) {add(i+n+p,TT,-y); total+=-y;}

     }

     add(TT,T,total);

     rep(i,,p)

     {

         string s; cin>>people_name[i]>>s>>s;

         if (s[s.length()-]==',') s.erase(s.end()-);

         cin.get(ch);

         if (ch=='\n') continue;

         string t; cin>>t;

         for (;;)

         {

             int x; cin>>x>>t;

             if (t[t.length()-]==',')

             {

                 t.erase(t.end()-);

                 people_has[i][res_number[t]]=x;

             }

             else

             {

                 people_has[i][res_number[t]]=x;

             }

             cin.get(ch);

             //cout<<(int)ch<<endl;

             if (cin.fail()) break;

             if (ch=='\n') break;

         }

         rep(j,,n)

         {

             //cout<<"\t"<<j<<" "<<people_has[i][j]<<" "<<build_need[build_number[s]][j]<<endl;

             int y=people_has[i][j]-build_need[build_number[s]][j];

             if (y>) add(i+n,n+p+j,y);

             if (y<) add(j,i+n,-y);

         }

     }

     rep(i,,n) add(n+p+i,i,INF);

     int x=dinic();

     #ifdef DEBUG

     cout<<x<<" "<<total<<endl;

     #endif

     if (x==total) {solve(S,); cout<<"build "<<my_build<<endl;}

     else cout<<"No way"<<endl;

 }

巴特西

codeforces gym 100357 J (网络流）

最新文章

热门文章