UVA735 TLE&&WA,,,,悲剧未完成,最大流

Posted by Cww97 on 2016-03-01

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50776461
题目点这
题意:输入n,有n个插座,下面n行是每个插座的类型(最后24个字母来表示一个插座,没有空格放心用scanf,但是有可能插座会相同,但是这个没有什么影响)
输入m,有m个电器,下面m行每行两个单词分别是电器的名字和插头类型(同样24个字母单词内没空格,两个单词空格隔开)
输入k,有k个转换器,下面k行每行两个单词,分别表示转换器的入口类型和插头类型
每种转换器的个数是无限的,转换器本身可以与转换器相连
要你求,让最多的电器能够插在插座上(可以用转换器辅助也可以直接插上去),输入不能插上去的电器的数量

分析
电器从1到m标号,转换器从m+1到m+k标号,插座从m+k+1到m+k+n标号,另外设置一个源点s=0,汇点t=m+k+n+1 , 求s到t的最大流s与所有电器建一条有向边,容量为1,所有插座与汇点建一条有向边,容量为1。对于每个电器,如果能直接和插座相连的,和每个能相连的插座建一条有向边,容量为1.另外,所有电器和所有能连接上的转换器建一条有向边,容量为INF,转换器和转换器之间能相连的建一条有向边容量为INF,转换器和插座能相连建一条有向边容量为INF。

写了一下午,,,WA,伤心
还不知道发生了什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
const int N=400,INF=999999;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int s,t,n,m,k;
string st,device[N],plug[N],adapter1[N],adapter2[N];
vector<Edge>edges;
vector<int>G[N];//邻接表
bool vis[N];//use when bfs
int d[N],cur[N];//dist,now edge

void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top=edges.size();
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}

bool BFS(){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}

int DFS(int x,int a){
if (x==t||a==0)return a;
int flow = 0,f;
for (int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f; a-=f;
if (a==0)break;
}
return flow;
}

int Maxflow(int s,int t){
int flow=0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow+=DFS(s,INF);
}
return flow;
}

int main(){
freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
for (int cas=1;cas<=T;cas++){
edges.clear();
for (int i=1;i<N;i++)G[i].clear();
scanf("%d\n",&n);//n个插座
for (int i=1;i<=n;i++)cin>>plug[i];
scanf("%d\n",&m);//m个设备
for (int i=1;i<=m;i++)cin>>st>>device[i];
scanf("%d\n",&k);//k种转换器
for (int i=1;i<=k;i++)cin>>adapter1[i]>>adapter2[i];

s=0;t=m+k+n+1;
for (int i=1;i<=m;i++){
AddEdge(0,i,1);
for (int j=1;j<=n;j++)
if (device[i]==plug[j])AddEdge(i,m+k+j,1);
for (int j=1;j<=k;j++)
if (device[i]==adapter1[j])AddEdge(i,m+j,INF);
}
for (int i=1;i<=k;i++){
for (int j=1;j<=n;j++)
if (adapter2[i]==plug[j])AddEdge(m+i,m+k+j,INF);
for (int j=1;j<=k;j++)
if (i!=j&&adapter2[i]==adapter1[j])AddEdge(m+i,m+j,INF);
}
for (int i=1;i<=n;i++)AddEdge(m+k+i,t,1);

int flow=Maxflow(s,t);
if (cas==T)printf("%d\n",m-flow);
else printf("%d\n\n",m-flow);
}
return 0;
}

然后改成EK算法,又tle了。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
const int N=400,INF=999999;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int s,t,n,m,k,a[N],p[N];
string st,device[N],plug[N],adapter1[N],adapter2[N];
vector<Edge>edges;
vector<int>G[N];//邻接表
bool vis[N];//use when bfs

void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top=edges.size();
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}

int Maxflow(int s,int t){
int flow=0;
for(;;){
memset(a,0,sizeof(a));
queue<int>Q;
Q.push(s);a[s]=INF;
while(!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (a[e.to]||e.cap<=e.flow)continue;
//printf("edge:from %d to %d cap %d flow %d\n",e.from,e.to,e.cap,e.flow);
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
Q.push(e.to);
}
if (a[t])break;
}
if (!a[t])break;
for (int x=t;x!=s;x=edges[p[x]].from){
edges[p[x] ].flow+=a[t];
edges[p[x]^1].flow-=a[t];
}
flow+=a[t];
}
//printf("flow=%d\n",flow);
return flow;
}

int main(){
freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
for (int cas=1;cas<=T;cas++){
edges.clear();
for (int i=1;i<N;i++)G[i].clear();
scanf("%d\n",&n);//n个插座
for (int i=1;i<=n;i++)cin>>plug[i];
scanf("%d\n",&m);//m个设备
for (int i=1;i<=m;i++)cin>>st>>device[i];
scanf("%d\n",&k);//k种转换器
for (int i=1;i<=k;i++)cin>>adapter1[i]>>adapter2[i];

s=0;t=m+k+n+1;
for (int i=1;i<=m;i++){
AddEdge(0,i,1);
for (int j=1;j<=n;j++)
if (device[i]==plug[j])AddEdge(i,m+k+j,1);
for (int j=1;j<=k;j++)
if (device[i]==adapter1[j])AddEdge(i,m+j,INF);
}
for (int i=1;i<=k;i++){
for (int j=1;j<=n;j++)
if (adapter2[i]==plug[j])AddEdge(m+i,m+k+j,INF);
for (int j=1;j<=k;j++)
if (i!=j&&adapter2[i]==adapter1[j])AddEdge(m+i,m+j,INF);
}
for (int i=1;i<=n;i++)AddEdge(m+k+i,t,1);

int flow=Maxflow(s,t);
if (cas==T)printf("%d\n",m-flow);
else printf("%d\n\n",m-flow);
}
return 0;
}

要开数组模拟存图吗,有功夫以后试试,心累
若有神犇路过,,您懂的