1.没有拆点
 2 5
 30 0 0 0 1
 40 0 0 0 1
 1 2 1 1 0
 50 1 0 1 1
 60 1 0 1 1
ans:1 2
2.当机器的一个输入性能点是1，可以与这台机器连线的合法机器对应的输出性能点必须是0
 3 2
 100 0 0 0 1 1 0
 100 0 1 0 1 1 1
ans:0 0
3.本人还写非常了弱智的代码：while(scanf("%d%d",&qn,&n)!=EOF)
开始没写成while(scanf("%d%d",&qn,&n)),结果输出超限 QAQ


AC代码：0ms 740k

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N=55;
const int M=N*N;
const int INF=0x3f3f3f3f;

struct mac{
	int q;
	int in[10],out[10];
}m[N];
struct edge{
	int v,next,c;
}e[M];
int p[2*N],eid;
int n,qn,g[2*N][2*N],cnt;

void add(int u,int v,int c){
	e[eid]={v,p[u],c}; p[u]=eid++;
	e[eid]={u,p[v],0}; p[v]=eid++;
}
int d[N],s,t;
bool bfs(){
	memset(d,-1,sizeof(d));
	queue<int> q;
	q.push(s); d[s]=0;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=p[u];~i;i=e[i].next){
			int v=e[i].v;
			if(e[i].c>0&&d[v]==-1){
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return d[t]!=-1;
}
int dfs(int u,int flow){
	if(u==t)return flow;
	int res=0;
	for(int i=p[u];~i;i=e[i].next){
		int v=e[i].v;
		if(e[i].c>0&&d[v]==d[u]+1){
			int tmp=dfs(v,min(e[i].c,flow));
			if(u!=s&&v!=t&&u>n&&v<=n&&tmp){
				if(g[u-n][v]==0) cnt++;
				g[u-n][v]+=tmp;
			}
			res+=tmp;
			flow-=tmp;
			e[i].c-=tmp;
			e[i^1].c+=tmp;
			if(!flow)break;
		}
	}
	if(!res) d[u]=-1;
	return res;
}

int main(){
	while(scanf("%d%d",&qn,&n)!=EOF){
		s=0,t=2*n+1;
		memset(p,-1,sizeof(p)); eid=0;
		memset(g,0,sizeof(g)); cnt=0;
		int flag;
		for(int i=1;i<=n;++i){
			scanf("%d",&m[i].q);
			for(int j=0;j<qn;++j)scanf("%d",&m[i].in[j]);
			for(int j=0;j<qn;++j)scanf("%d",&m[i].out[j]); 
		}
		for(int i=1;i<=n;++i)
			add(i,i+n,m[i].q);
		for(int i=1;i<=n;++i){
			int k;
			for(k=0;k<qn;++k) 
				if(m[i].in[k]==1)break;
			if(k==qn) add(s,i,m[i].q);
			for(k=0;k<qn;++k)
				if(m[i].out[k]==0)break;
			if(k==qn) {
				add(i+n,t,m[i].q);
				continue;
			}
			for(int j=1;j<=n;++j){
				if(i==j)continue;
				flag=0;
				for(k=0;k<qn;++k){
					if(m[j].in[k]&&m[i].out[k]){
						flag=1;
					}else if(m[j].in[k]==1&&!m[i].out[k]||m[j].in[k]==0&&m[i].out[k]){
						flag=0;
						break;
					}
				}
				if(flag) add(i+n,j,m[i].q);
			}
		}
		int ans=0;
		while(bfs()) {
			ans+=dfs(s,INF);
	//		cout<<ans<<endl;
		}
		printf("%d %d\n",ans,cnt);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(i==j)continue;
				if(g[i][j])printf("%d %d %d\n",i,j,g[i][j]);
			}
		}
	}
	return 0;
}

• 拆点的数据给力 (15) forestgump2012 2022-02-24 11:40:52