HDU - 2828 网络流

题目大意

　　有n个灯，m个开关，由于线路乱接导致可能有多个开关对应一个灯（并联），有的灯在开关开的时候亮

　　有的灯在开关关的时候亮，【每个开关最多对应两盏灯】，试找出一种开关的ON，OFF状态，使得所有灯都亮。

　　（注意不要漏读黑框内的内容）

解法1：网络流

　　对于一个开关有一下几种情况：

　　1.开关只连向一个灯，直接设定开关点亮此灯。

　　2.开关连向两个开关状态需求相同的灯，直接把开关拨到相应状态，点亮两个灯。

　　3.开关连向两个需求不同冲突的灯，（只能选择两者之一点亮）。

　　接下来网络流即可【注意区分n，m】

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <queue>

 #define N 1010

 #define INF 0x3f3f3f3f

 #define p E[i].x

 using namespace std;

 int n,m,S,T,totE;

 int sw[N],g[N],d[N];

 bool v[N];

 vector<int> a[][N];

 queue<int> q;

 struct edge

 {

     int x,to,cap;

 }E[];

 void addedge(int x,int y,int cap)

 {

     E[++totE] = (edge){y,g[x],cap}; g[x]=totE;

     E[++totE] = (edge){x,g[y],};    g[y]=totE;

 }

 bool bfs()

 {

     memset(v,,sizeof(v));

     d[S]=;

     v[S]=;

     q.push(S);

     while(!q.empty())

     {

         int x=q.front(); q.pop();

         for(int i=g[x];i;i=E[i].to)

             if(E[i].cap && !v[p])

             {

                 v[p]=;

                 d[p]=d[x]+;

                 q.push(p);

             }

     }

     return v[T];

 }

 int dinic(int x,int flow)

 {

     if(x==T || !flow) return flow;

     int f=;

     for(int i=g[x];i&&flow;i=E[i].to)

         if(d[p]==d[x]+&&E[i].cap)

         {

             int tmp=dinic(p,min(flow,E[i].cap));

             f+=tmp;

             flow-=tmp;

             E[i].cap-=tmp;

             E[i^].cap+=tmp;

         }

     if(!f) d[x]=-;

     return f;

 }

 int main()

 {

 //    freopen("test.txt","r",stdin);

     while(~scanf("%d%d",&n,&m))

     {

         memset(g,,sizeof(g));

         totE=;

         for(int i=;i<=m;i++)

         {

             sw[i]=;

             a[][i].clear();

             a[][i].clear();

         }

         char cmd[];

         for(int i=,x,K;i<=n;i++)

         {

             scanf("%d",&K);

             while(K--)

             {

                 scanf("%d%s",&x,cmd);

                 int tmp;

                 if(cmd[]=='N') tmp=;

                 else tmp=;

                 a[tmp][x].push_back(i);

             }

         }

         S=;

         T=n+m+;

         for(int i=;i<=n;i++) addedge(i+m,T,);

         for(int i=;i<=m;i++)

         {

             if(a[][i].size()== && a[][i].size()==)

             {

                 addedge(S,i,);

                 sw[i]=-;

                 addedge(i,m+a[][i][],);

                 addedge(i,m+a[][i][],);

             }

             else if(a[][i].size()==)

             {

                 addedge(S,i,);

                 sw[i]=;

                 addedge(i,m+a[][i][],);

                 addedge(i,m+a[][i][],);

             }

             else if(a[][i].size()==)

             {

                 addedge(S,i,);

                 sw[i]=;

                 addedge(i,m+a[][i][],);

                 addedge(i,m+a[][i][],);

             }

             else

             {

                 addedge(S,i,);

                 if(a[][i].size())         sw[i]=, addedge(i,m+a[][i][],);

                 else if(a[][i].size()) sw[i]=, addedge(i,m+a[][i][],);

                 else sw[i]=;

             }

         }

         int ans=;

         while(bfs()) ans+=dinic(S,INF);

         if(ans<n) puts("-1");

         else

         {

             for(int i=;i<=totE;i+=)

             {

                 if(E[i].cap) continue;

                 int x=E[i^].x, y=E[i].x;

                 if(sw[x]!=-) continue;

                 //cout << x << ' ' << y-m<<endl;

                 if(x<=m && x>=)

                 {

                     if(y-m == a[][x][]) sw[x]=;

                     else sw[x]=;

                 }

             }

             for(int i=;i<=m;i++)

             {

                 if(sw[i]) printf("ON%c",i==m? '\n':' ');

                 else printf("OFF%c",i==m? '\n':' ');

             }

         }

     }

     return ;

 }

解法2：DLX

巴特西

HDU - 2828 网络流

最新文章

热门文章