HDU

题目大意

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

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

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

解法1：网络流

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

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

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

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

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <queue>
  6 
  7 #define N 1010
  8 #define INF 0x3f3f3f3f
  9 #define p E[i].x
 10 
 11 using namespace std;
 12 
 13 int n,m,S,T,totE;
 14 int sw[N],g[N],d[N];
 15 bool v[N];
 16 vector<int> a[2][N];
 17 queue<int> q;
 18 
 19 struct edge
 20 {
 21     int x,to,cap;
 22 }E[200010];
 23 
 24 void addedge(int x,int y,int cap)
 25 {
 26     E[++totE] = (edge){y,g[x],cap}; g[x]=totE;
 27     E[++totE] = (edge){x,g[y],0};    g[y]=totE;
 28 }
 29 
 30 bool bfs()
 31 {
 32     memset(v,0,sizeof(v));
 33     d[S]=1;
 34     v[S]=1;
 35     q.push(S);
 36     while(!q.empty())
 37     {
 38         int x=q.front(); q.pop();
 39         for(int i=g[x];i;i=E[i].to)
 40             if(E[i].cap && !v[p])
 41             {
 42                 v[p]=1;
 43                 d[p]=d[x]+1;
 44                 q.push(p);
 45             }
 46     }
 47     return v[T];
 48 }
 49 
 50 int dinic(int x,int flow)
 51 {
 52     if(x==T || !flow) return flow;
 53     int f=0; 
 54     for(int i=g[x];i&&flow;i=E[i].to)
 55         if(d[p]==d[x]+1&&E[i].cap)
 56         {
 57             int tmp=dinic(p,min(flow,E[i].cap));
 58             f+=tmp;
 59             flow-=tmp;
 60             E[i].cap-=tmp;
 61             E[i^1].cap+=tmp;
 62         }
 63     if(!f) d[x]=-1;
 64     return f;
 65 }
 66 
 67 int main()
 68 {
 69 //    freopen("test.txt","r",stdin);
 70     while(~scanf("%d%d",&n,&m))
 71     {
 72         memset(g,0,sizeof(g));
 73         totE=1;
 74         for(int i=1;i<=m;i++)
 75         {
 76             sw[i]=0;
 77             a[0][i].clear();
 78             a[1][i].clear();
 79         }
 80         char cmd[11];
 81         for(int i=1,x,K;i<=n;i++)
 82         {
 83             scanf("%d",&K);
 84             while(K--)
 85             {
 86                 scanf("%d%s",&x,cmd);
 87                 int tmp;
 88                 if(cmd[1]=='N') tmp=1;
 89                 else tmp=0;
 90                 a[tmp][x].push_back(i);
 91             }
 92         }
 93         S=0;
 94         T=n+m+1;
 95         for(int i=1;i<=n;i++) addedge(i+m,T,1);
 96         for(int i=1;i<=m;i++)
 97         {
 98             if(a[0][i].size()==1 && a[1][i].size()==1)
 99             {
100                 addedge(S,i,1);
101                 sw[i]=-1;
102                 addedge(i,m+a[0][i][0],1);
103                 addedge(i,m+a[1][i][0],1);
104             }
105             else if(a[0][i].size()==2)
106             {
107                 addedge(S,i,2);
108                 sw[i]=0;
109                 addedge(i,m+a[0][i][0],1);
110                 addedge(i,m+a[0][i][1],1);
111             }
112             else if(a[1][i].size()==2)
113             {
114                 addedge(S,i,2);
115                 sw[i]=1;
116                 addedge(i,m+a[1][i][0],1);
117                 addedge(i,m+a[1][i][1],1);
118             }
119             else
120             {
121                 addedge(S,i,1);
122                 if(a[1][i].size())         sw[i]=1, addedge(i,m+a[1][i][0],1);
123                 else if(a[0][i].size()) sw[i]=0, addedge(i,m+a[0][i][0],1);
124                 else sw[i]=0;
125             }
126         }
127         int ans=0;
128         while(bfs()) ans+=dinic(S,INF);
129         if(ans<n) puts("-1");
130         else
131         {
132             for(int i=2;i<=totE;i+=2)
133             {
134                 if(E[i].cap) continue;
135                 int x=E[i^1].x, y=E[i].x;
136                 if(sw[x]!=-1) continue;
137                 //cout << x << ' ' << y-m<<endl;
138                 if(x<=m && x>=1)
139                 {
140                     if(y-m == a[0][x][0]) sw[x]=0;
141                     else sw[x]=1;
142                 }
143             }
144             for(int i=1;i<=m;i++)
145             {
146                 if(sw[i]) printf("ON%c",i==m? '
':' ');
147                 else printf("OFF%c",i==m? '
':' ');
148             }
149         }
150     }
151     return 0;
152 }

View Code

解法2：DLX