C++14(g++5.4) 解法, 执行用时: 48ms, 内存消耗: 348K, 提交时间: 2020-07-14 16:01:04

// Created by CAD on 2020/7/14.
#include <bits/stdc++.h>

#define fi first
#define se second
#define pii pair<int,int>
using namespace std;

vector<pii> g[55];
int d[55],id[55],n,vis[105];
bool cmp(int a,int b){
    return g[a].size()<g[b].size();
}
bool dfs(int x){
    int p=id[x];
    if(x>n) return 1;
    if(!d[p]) return dfs(x+1);
    for(auto i:g[p]){
        int v=i.fi,e=i.se;
        if(!d[v]||vis[e]) continue;
        d[p]--,d[v]--,vis[e]=1;
        if(dfs(x)) return 1;
        d[p]++,d[v]++,vis[e]=0;
    }
    return 0;
}

int main() {
    int m;
    while(cin>>n>>m){
        for(int i=1;i<=n;++i)
            cin>>d[i],id[i]=i,g[i].clear();
        for(int i=1;i<=m;++i){
            int a,b;cin>>a>>b;
            g[a].push_back({b,i});
            g[b].push_back({a,i});
            vis[i]=0;
        }
        sort(id+1,id+n+1,cmp);
        if(dfs(1)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 953ms, 内存消耗: 400K, 提交时间: 2023-04-29 17:22:33

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[55][55],d[55],id[55],siz[55];
bool dfs(int x){
	int u=id[x];
	if(x>n)return 1;
	if(d[u]==0)return dfs(x+1);
	for(int i=1;i<=n;i++){
		if(vis[u][i]){
			if(!d[i])continue;
			d[i]--,d[u]--,vis[u][i]=vis[i][u]=0;
			if(dfs(x))return 1;
			d[i]++,d[u]++,vis[u][i]=vis[i][u]=1;
		}
	}
	return 0;
}

bool cmp(int x,int y){
	return siz[x]<siz[y];
}
void solve(){
	for(int i=1;i<=n;i++)cin>>d[i],id[i]=i;
	memset(siz,0,sizeof(siz));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		vis[u][v]=vis[v][u]=1;
		siz[u]++,siz[v]++;
	}
	bool flag=1;
	sort(id+1,id+1+n,cmp);
	if(dfs(1))cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	while(cin>>n>>m)
		solve();
}

C++(clang++11) 解法, 执行用时: 45ms, 内存消耗: 444K, 提交时间: 2020-10-21 17:03:38

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=101;
int n,m,d[N],id[N];bool used[N];
vector<pair<int,int> >e[N];
bool dfs(int dep){
	if(dep>n)return 1;int u=id[dep];
	if(!d[u])return dfs(dep+1);
	for(auto edg:e[u]){
		int v=edg.first,num=edg.second;
		if(!d[v]||used[num])continue;
		d[u]--,d[v]--,used[num]=1;
		if(dfs(dep))return 1;
		d[u]++,d[v]++,used[num]=0;
	}
	return 0;
}
bool cmp(int a,int b){
	return e[a].size()<e[b].size();
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++)scanf("%d",&d[i]),id[i]=i,e[i].clear();
		for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),e[u].push_back(pair<int,int>(v,i)),
		e[v].push_back(pair<int,int>(u,i)),used[i]=0;
		sort(id+1,id+n+1,cmp);
		printf("%s\n",dfs(1)?"Yes":"No");
	}

}